分数: 100 点
问题陈述
你知道吗 正奇发明有限公司?这家公司只从事奇怪的发明。 我们将其缩写为 JOI。
在 JOI 的一个实验室里,有一个复杂的电路。 该电路由 N 节点和 M 薄电阻器。 节点已编号 0 通过 N - 1,电阻器编号 0 通过 M - 1。 每个节点可以设置为以下两种状态之一: 高电压 or 低电压。 电阻器 i (0 \leq i \leq M - 1) 从节点连接 A_i 到另一个节点 B_i。 电流流过该电阻当且仅当节点 A_i 设置为高电压和节点 B_i 设置为低电压。 在所有其他情况下,没有电流流过它。 另外,对于任意两个节点,最多有一个电阻连接它们,无论其方向如何。
您是 JOI 的研究员,您将使用该电路进行实验。 电路中的电阻器非常细,您无法直观地确定它们连接的是哪对节点。 然而,有一个线索:在设置电压时,电路的温度会根据电流流过的电阻器的数量而升高。 因此,设置电压后,您决定触摸电路并读取其温度。 虽然您无法测量电路的准确温度,但您可以执行两种电压设置并比较哪一种使电路更热。 也就是说,通过指定两个电压设置,您可以获得以下信息之一:
- 在第一电压设置中,电流流过的电阻器的数量较大。
- 在两种电压设置下,电流流过的电阻数量相同。
- 在第二电压设置中,电流流过的电阻器的数量更大。
您的目标是重复此类温度比较并确定电路中的所有电阻器,即所有有序对 (a, b) 使得节点有一个电阻 a 到节点 b。 预先给定您节点的数量 N 和电阻器的数量 M。 您还知道每个电阻器连接两个不同的节点,并且对于任何两个节点,最多有一个电阻器连接它们,无论方向如何。 在这些条件下,确定整个有序对集合 (a, b) 对应电路中的电阻,从温度比较得到的信息。 请注意,根据电路的结构,无论进行何种比较或进行多少次比较,都可能无法唯一地确定电阻器。 在这种情况下,您必须报告不可能唯一地确定它们。
为防止电阻劣化,最多允许比较温度 30\,000 次。
顺便说一句,JOI用这个奇怪的电路做出什么样的发明,即使在公司内部也是最高机密,除了总裁之外没有人知道。
给定电路中的节点和电阻器的数量,编写一个程序来确定电路中的电阻器,或者报告这是不可能的,最多使用 30\,000 温度比较。
实施细节
您提交的计划必须包括 voltage.h 使用 #include 预处理器指令,并且必须实现以下函数。
-
bool solve(int N, int M)- 该函数在每次执行中仅调用一次。
- 论点
N表示电路中的节点数, N. - 论点
M表示电路中电阻的数量, M. - 该函数必须返回
false如果无论进行多少次温度比较都无法唯一确定电阻器连接;否则,它必须返回true. - 如果此函数返回
true当无法唯一确定电阻连接时,您的程序被判断为 错误答案 [1]. - 如果此函数返回
false尽管可以通过温度比较确定电路,但您的程序被判断为 错误答案 [2].
您的程序可能会调用以下函数。
-
int query(std::vector<int> x, std::vector<int> y)- 通过使用此功能,您可以执行两个电压设置并比较它们的温度。
- 论点
x指定第一个电压设置,参数y指定第二个电压设置。 - 论点
x和y必须是长度数组 N 组成 0的和 1的。 - If
x[k](0 \leq k \leq N - 1) 是 1,然后在第一个电压设置中,节点 k 设置为高电压; 如果x[k]is 0,然后节点 k 设置为低电压。 - If
y[k](0 \leq k \leq N - 1) 是 1,然后在第二个电压设置中,节点 k 设置为高电压; 如果y[k]is 0,然后节点 k 设置为低电压。 - 该函数的返回值是比较第一和第二电压设置下电路温度的结果,并且是以下之一 -1, 0,或 1.
- 如果返回值为 -1,则电流流过的电阻器的数量在第一电压设置中比在第二电压设置中更大。
- 如果返回值为 0,则在第一和第二电压设置下电流流过的电阻器的数量相等。
- 如果返回值为 1,则第二电压设置中电流流过的电阻器的数量大于第一电压设置中的电流流过的电阻器的数量。
x 不是 N,你的程序被判断为 错误答案 [3].
x 包含的值不是 0 or 1,你的程序被判断为 错误答案 [4].
y 不是 N,你的程序被判断为 错误答案 [5].
y 包含的值不是 0 or 1,你的程序被判断为 错误答案 [6].
void answer(int a, int b)
- 使用此功能报告您已识别的电阻器。
- 论点
a和b表示有一个来自节点的电阻 a 到节点 b. - 必须认为 0 \leq a \leq N - 1 和 0 \leq b \leq N - 1。 如果不满足这个条件,你的程序被判定为 错误答案 [8].
- 不得使用同一对调用此函数两次或多次 (a, b)。 如果违反这个条件,你的程序将被判定为 错误答案 [9].
- 调用此函数的次数不得超过 M 次。 如果这个函数被调用超过 M 次,你的程序被判定为 错误答案 [10].
- 当该功能
solve返回true,函数answer必须被准确调用 到那时 M 次。 如果不满足这个条件,你的程序被判定为 错误答案 [11]. - 当该功能
solve返回true,对于每对 (a, b) 作为参数传递给answer到目前为止,实际上必须存在一个从节点定向的电阻器 a 到节点 b。 如果不满足这个条件,你的程序被判定为 错误答案 [12].
重要通知
- 您可以实现其他辅助函数或声明全局变量以供内部使用。
- 您提交的程序不得使用标准输入/输出或任何其他文件交互。但是,您可以使用标准错误输出进行调试。
编译与执行
您可以从竞赛网页下载存档文件,其中包含用于测试您的程序的示例评分器。存档文件还包含程序的示例源文件。
示例评分器是文件 grader.cpp。要测试您的程序,请将文件 grader.cpp, voltage.cpp,和 voltage.h 在同一目录中,并使用以下命令编译它们:
g++ -std=gnu++20 -O2 -o grader grader.cpp voltage.cpp
或者,您可以执行
通过运行以下命令将 compile.sh 文件包含在存档中:
./compile.sh
如果编译成功,会生成一个名为
将生成 grader 。
请注意,实际评分器与示例评分器不同。 示例分级器作为单个进程启动,它将从标准输入读取输入数据并将结果写入标准输出。
样本分级机的输入
示例评分器按以下格式从标准输入读取输入:
N M
A_0 B_0
\vdots
A_{M-1} B_{M-1}
样本分级机的输出
示例分级器将以下信息输出到标准输出(实际输出中不包含引号)。
- 如果您的程序被判断为错误答案 [3] – [12] 之一,则错误答案的类型将打印为“
Wrong Answer [5]". - 否则,调用该函数的次数
query和函数的返回值solve打印为“Accepted: 30 true“。 样本评分者与实际评分者不同,不会判断结论应该是错误答案[1]还是[2],即函数的返回值是否solve是正确的。
一旦满足错误答案 [3] – [12] 的任何条件,样本评分器就会终止执行。 如果满足多个不正确的条件,则仅显示其中之一。
评分通知
实际分级机不自适应;从交互一开始就有一个固定的答案。
约束
- 2 \leq N \leq 600.
- 1 \leq M \leq 1\,000.
- 0 \leq A_i \leq N - 1 (0 \leq i \leq M - 1).
- 0 \leq B_i \leq N - 1 (0 \leq i \leq M - 1).
- A_i \neq B_i (0 \leq i \leq M - 1).
- (A_i, B_i) \neq (A_j, B_j) 和 (A_i, B_i) \neq (B_j, A_j) (0 \leq i < j \leq M - 1).
- N, M, A_i,和 B_i 是整数 (0 \leq i \leq M - 1).
子任务
- (10分) N \leq 100, M = N - 1, B_i = A_{i+1} (0 \leq i \leq N - 3),以及 N 值 A_0, A_1, \ldots, A_{N-2}, B_{N-2} 都是不同的。
- (12分) M = N - 1, B_i = A_{i+1} (0 \leq i \leq N - 3),以及 N 值 A_0, A_1, \ldots, A_{N-2}, B_{N-2} 都是不同的。
- (27分) N \leq 100, A_i \neq A_j (0 \leq i < j \leq M - 1).
- (18分) A_i \neq A_j (0 \leq i < j \leq M - 1).
- (17分) N \leq 100.
- (16 分) 没有额外的限制。
交互示例
下面是示例评分器读取的输入和相应函数调用的示例。
示例输入 1
5 6 0 2 2 1 0 3 3 2 3 4 4 1

在第一次调用 query,两种电压设置和电流流过的电阻如下。
- 在第一个设置中,节点 0 和 1 设置为低电压,并且节点 2, 3,和 4 设置为高电压。 此时,电流流过电阻 1 和 5.
- 在第二个设置中,节点 3 和 4 设置为低电压,并且节点 0, 1,和 2 设置为高电压。 此时,电流流过电阻 2.
由于第一个电压设置时电流流过的电阻数量较多,因此返回值为 -1.
此示例输入满足子任务的约束 5, 6.
可从竞赛网站下载的文件包括: sample-01-in.txt 对应于样本输入 1。
另外, sample-02-in.txt 满足所有子任务的约束,并且 sample-03-in.txt 满足子任务的约束 3, 4, 5, 6.