AdditionalFile5674.zip

#5674. 「JOI 2026 Final Day4」电压 2

标签: 交互 | 时间限制: 2000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 JOI 2026 Final Day4 T3 「電圧 2 / Voltage 2」

你听说过 Just Odd Inventions 公司吗？这家公司的业务正如其名，专门从事「奇妙发明（just odd inventions）」。以下简称为 JOI 社。

在 JOI 社的某个实验室里，有一套复杂的电路。该电路由 $N$ 个节点和 $M$ 条细长的电阻组成，节点编号为 $0$ 到 $N-1$，电阻编号为 $0$ 到 $M-1$。每个节点的状态都可以被设定为高电压或低电压。第 $i$ $(0 \leq i \leq M-1)$ 条电阻从节点 $A_i$ 连接到与之不同的节点 $B_i$，且只有当节点 $A_i$ 处于高电压而节点 $B_i$ 处于低电压状态时，该电阻中才会有电流流过。在其他情况下，电阻中没有电流。此外，已知任意两个节点之间，无论方向如何，最多只存在一条电阻。

作为 JOI 社的一名研究员，你被指派利用这套电路进行实验。由于电阻极其细长，你无法通过肉眼直接确认电阻连接的是哪些节点。不过，你拥有一个线索：在设定各节点电压时，电路的温度会根据有电流流过的电阻数量而上升。因此，你决定在设定电压后，通过接触电路来感知温度。虽然你无法精确读出电路的温度值，但你可以先后进行两次电压设定，并比较哪一次设定的温度更高。也就是说，通过指定两组电压设定，你可以获得以下信息之一：

• 第一次设定的电压下，流过电流的电阻数量更多。
• 两次电压设定下，流过电流的电阻数量相同。
• 第二次设定的电压下，流过电流的电阻数量更多。

你的目标是通过重复这种温度比较，确定所有电阻分别是从哪个节点连接到哪个节点的。节点数 $N$ 和电阻数 $M$ 是预先给出的。已知电阻连接的是不同的节点，且任意两个节点之间最多只有一条电阻。在这些条件下，请根据温度比较获得的信息，确定电路中存在的所有电阻连接节点对 $(a, b)$。需要注意的是，根据电路结构的不同，无论进行多少次比较，可能都无法唯一确定电阻的连接情况。在这种情况下，你需要报告无法确定。

为了防止电阻老化，实际允许进行的温度比较次数不得超过 $30000$ 次。

顺便一提，关于 JOI 社利用这种奇妙电路在进行什么发明，这在公司内部属于最高机密，除了社长以外无人知晓。

给定电路的节点数和电阻数，请编写一个程序，通过不超过 $30000$ 次的温度比较，确定电路的电阻连接情况，或者报告无法确定。

实现细节

你的程序必须包含 #include "voltage.h"，并实现以下函数：

• bool solve(int N, int M)
  • 该函数在每次运行中仅被调用一次。
  • 参数 $N$ 是电路的节点数。
  • 参数 $M$ 是电路的电阻数。
  • 如果无论进行多少次温度比较都无法唯一确定电阻的连接情况，该函数应返回 false；否则应返回 true。
  • 如果在可以确定的情况下返回了 false，则判定为 Wrong Answer [2]。
  • 如果在无法确定的情况下返回了 true，则判定为 Wrong Answer [1]。

你的程序可以调用以下函数：

• int query(std::vector<int> x, std::vector<int> y)

  • 你可以使用此函数进行两次电压设定并比较温度。
  • 参数 $x$ 指定第一次电压设定，参数 $y$ 指定第二次电压设定。
  • 参数 $x$ 和 $y$ 必须是长度为 $N$ 且仅包含 $0$ 和 $1$ 的数组。
  • 当 $x[k] = 1$ $(0 \leq k \leq N-1)$ 时，表示在第一次设定中将节点 $k$ 设为高电压；当 $x[k] = 0$ 时，表示设为低电压。$y[k]$ 对第二次设定的含义相同。
  • 该函数的返回值是两次设定下温度比较的结果，值为 $-1, 0, 1$ 之一：
    • 返回值为 $-1$ 时，表示第一次设定下有电流流过的电阻数量多于第二次。
    • 返回值为 $0$ 时，表示两次设定下有电流流过的电阻数量相等。
    • 返回值为 $1$ 时，表示第二次设定下有电流流过的电阻数量多于第一次。
  • 当参数 $x$ 的长度不为 $N$ 时，判定为 Wrong Answer [3]。
  • 当参数 $x$ 中包含非 $0$ 或 $1$ 的值时，判定为 Wrong Answer [4]。
  • 当参数 $y$ 的长度不为 $N$ 时，判定为 Wrong Answer [5]。
  • 当参数 $y$ 中包含非 $0$ 或 $1$ 的值时，判定为Wrong Answer [6]。
  • 该函数的调用次数不得超过 $30000$ 次。如果超过 $30000$ 次，判定为 Wrong Answer [7]。

• void answer(int a, int b)

  • 使用此函数提交你确定的电阻连接情况。
  • 参数 $a, b$ 表示存在一条从节点 $a$ 连接到节点 $b$ 的电阻。
  • 必须满足 $0 \leq a \leq N-1$ 且 $0 \leq b \leq N-1$，否则判定为 Wrong Answer [8]。
  • 不得使用相同的 $(a, b)$ 组合多次调用此函数，否则判定为 Wrong Answer [9]。
  • 该函数的调用次数不得超过 $M$ 次，否则判定为 Wrong Answer [10]。
  • 当函数 solve 返回 true 时，在此之前必须恰好调用了 $M$ 次 answer 函数。如果调用次数不符，判定为 Wrong Answer [11]。
  • 当函数 solve 返回 true 时，此前通过 answer 提交的所有 $(a, b)$ 组合必须与电路中实际存在的电阻连接情况一致。如果存在错误连接，判定为 Wrong Answer [12]。

注意事项

• 你可以根据需要自由定义其他函数或全局变量。
• 你的程序不得通过标准输入输出或其他文件进行交互。允许向标准错误输出（stderr）输出调试信息。

编译与运行

你可以从「文件」下载用于测试程序的示例评测程序。该压缩包中也包含你需要提交的程序示例。

示例评测程序包含 grader.cpp。要测试你的程序，请将 grader.cpp、voltage.cpp 和 voltage.h 放在同一目录下，并执行以下命令：

g++ -std=gnu++20 -O2 -o grader grader.cpp voltage.cpp

你也可以运行压缩包内的 compile.sh。编译成功后将生成可执行文件 grader。

请注意，实际的评测程序与示例评测程序不同。示例评测程序作为一个单进程启动，从标准输入读取数据，并将结果输出到标准输出。

输入格式

示例评测程序按以下格式读取输入：

第一行包含两个整数 $N, M$。

接下来的 $M$ 行，其中第 $i$ 行包含两个整数 $A_i, B_i$。

输出格式

示例评测程序将以下信息输出到标准输出：

• 如果发生 Wrong Answer [3]~[12] 中的任意一种，将输出错误类型，例如 Wrong Answer [5]。
• 否则，将输出 query 的调用次数以及 solve 的返回值，例如 Accepted: 30 true。注意，示例评测程序与实际评测程序不同，它不会判断 solve 的返回值是否正确（即不判定 Wrong Answer [1] 和 [2]）。

样例

以下是示例评测程序读取的输入以及对应的函数调用示例。

5 6
0 2
2 1
0 3
3 2
3 4
4 1

直译：在第一次 query 调用中，两次电压设定和有电流流过的电阻情况如下：

• 第一次设定：将节点 $0, 1$ 设为低电压，节点 $2, 3, 4$ 设为高电压。此时电阻 $1$ (连接节点 $2 \to 1$) 和电阻 $5$ (连接节点 $4 \to 1$) 有电流流过（总共 $2$ 条）。
• 第二次设定：将节点 $3, 4$ 设为低电压，节点 $0, 1, 2$ 设为高电压。此时电阻 $2$ (连接节点 $0 \to 3$) 有电流流过（总共 $1$ 条）。

由于第一次设定下电流流过的电阻数量更多，因此返回值为 $-1$。 该样例满足子任务 $5, 6$ 的限制。

数据范围与提示

实际的评测程序是非适应性的（non-adaptive），即答案在交互开始前已经固定。

详细子任务附加限制及分值如下表所示。