题目描述

题目译自 JOISC 2023 Day2 T1 「ベルトコンベア / Belt Conveyor」

JOI 公司的工厂里有 $N$ 张桌子，编号为 $0$ 到 $N-1$。在工厂里，有 $N-1$ 条传送带，编号为 $0$ 到 $N-2$。传送带 $i\ (0\le i\le N-2)$ 连接桌子 $A_i$ 和 $B_i$。传送带会从一个桌子向另一个桌子传送产品。然而，我们不知道传送的方向。如果我们忽略传送带的方向，每对桌子被一些传送带所连接。

IOI 君是工厂的厂长。因为它忘了每个传送带的传送方向，他将按顺序进行如下操作几次：

1. 他选择一些传送带，并反转这些传送带的传送方向。
2. 他选择一些桌子，每个桌子放置一个产品。
3. 对于每个他放了产品的桌子，会同时发生以下情况中的一个：
   • 如果没有传送带从这个桌子出发，什么都不会发生。
   • 如果有传送带从这个桌子出发，在这个桌子上的产品会被一个这样的传送带传送。这个产品会停在这条传送带的终点。这个产品不会再移动。
4. IOI 君会确认每个桌子上是否有一个及以上产品。如果桌子上有产品，IOI 君会收走全部产品。
5. 对于在第 1 步操作中反向的传送带，IOI 君会回退它的方向。之后所有传送带的方向的最初的方向相同。

IOI 君希望通过最多 $30$ 次操作确定每条传送带最初的方向。

给定连接桌子的传送带的信息，写一个程序实现 IOI 君确定原来传送带方向的策略，最多进行上述操作 $30$ 次。

实现细节

你需要提交一个文件，文件名为 conveyor.cpp。

首先你应该在文件开头引入头文件 conveyor.h。

#include "conveyor.h"

在 conveyor.cpp 中，你应该实现如下函数。

• void Solve(int N, std::Vector<int> A, std::vector<int> B)

  每组测试用例会调用这个函数一次

  • 参数 N 表示桌子的数量 $N$
  • 参数 A，B 是长为 $N-1$ 的数组，描述被传送带连接的桌子。

你的程序可以调用如下函数。

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

  使用这个函数，IOI 君可以在工厂中进行操作

  • 参数 x 是长为 $N-1$ 的数组。对于 $0\le \texttt i\le N-2$，如果 x[i] = 1，那么 IOI 君会反转传送带 $\texttt i$ 的方向，如果 x[i] = 0，则不反转
  • 参数 y 是长为 $N$ 的数组。对于 $0\le \texttt j\le N-1$，如果 y[j] = 1，那么 IOI 君会在桌子 $\texttt j$ 上放一个产品，如果 y[j] = 0，则不放
  • 令 z 表示这个函数的返回值。这是一个长为 N 的数组。对于 $0\le \texttt j\le N-1$，如果桌子 $\texttt j$ 上有一个及以上产品，则 z[j] = 1，否则 z[j] = 0
  • 数组 x 的长度应当等于 $N-1$。如果此条件不满足，你的程序将被判为 Wrong Answer [1]
  • 数组 x 中每个元素应当为 0 或 1。如果此条件不满足，你的程序将被判为 Wrong Answer [2]
  • 数组 y 的长度应当等于 $N$。如果此条件不满足，你的程序将被判为 Wrong Answer [3]
  • 数组 y 中每个元素应当为 0 或 1。如果此条件不满足，你的程序将被判为 Wrong Answer [4]
  • 函数 Query 不应该调用超过 $30$ 次。如果此条件不满足，你的程序将被判为 Wrong Answer [5]

• void Answer(std::vector<int> a)

  使用这个函数，IOI 君可以报告每条传送带的初始方向

  • 参数 a 是长为 $N-1$ 的数组。对于 $0\le \texttt i\le N-2$，如果 a[i] = 0，那么传送带 $\texttt i$ 运输的方向是从 $A_i$ 到 $B_i$，如果 x[i] = 0，则为 $B_i$ 到 $A_i$
  • 数组 a 的长度应当等于 $N-1$。如果此条件不满足，你的程序将被判为 Wrong Answer [6]
  • 数组 a 中每个元素应当为 0 或 1。如果此条件不满足，你的程序将被判为 Wrong Answer [7]
  • 如果 IOI 君报告的传送带方向是错误的，你的程序将被判为 Wrong Answer [8]
  • 函数 Answer 应该仅被调用一次。如果函数 Answer 被调用超过一次，你的程序将被判为 Wrong Answer [9]。当函数 Solve 结束时，如果函数 Answer 没有被调用，你的程序将被判为 Wrong Answer [10]

注意事项

• 你的程序可以实现其他函数以供内部使用，或者使用全局变量
• 你的程序不得使用标准输入输出。你的程序不得以任何方式与其他文件通信。然而，你的程序可以向标准错误输出输出调试信息。

编译和测试运行

你可以从「文件」页面下载样例交互器并测试你的程序。「文件」页面也包含一个样例源文件。

样例交互器是文件 grader.cpp。为了测试你的程序，你需要将 grader.cpp，conveyor.cpp 和 conveyor.h 三个文件放在同一文件夹下，并运行如下命令编译你的程序。你也可以运行 compile.sh 代替如下命令编译你的程序

g++ -std=gnu++17 -O2 -o grader grader.cpp conveyor.cpp

当编译成功后，会产生一个可执行文件 grader。

请注意实际的交互器和样例交互器不同。样例交互器会以单进程的形式执行，它会从标准输入中读入，并输出结果到标准输出。

样例交互器输入

样例交互器从标准输入读入以下内容。

第一行一个整数 $N$。

第二行 $N-1$ 个整数 $A_0,A_1,\ldots,A_{N-2}$。

第三行 $N-1$ 个整数 $B_0,B_1,\ldots,B_{N-2}$。

第四行 $N-1$ 个整数 $C_0,C_1,\ldots,C_{N-2}$。

对于 $0\le i\le N-2$，如果传送带 $i$ 从 $A_i$ 将产品运向 $B_i$，则 $C_i=0$，否则 $C_i=1$。

样例交互器输出

样例交互器输出如下信息到标准输出。

• 如果你的程序被判为正确，它将输出调用 Query 函数的次数，如 Accepted: 22。
• 如果你的程序被判为错误，它将输出错误类别，如 Wrong Answer [4]

如果你的程序满足多种答案错误的类别，样例交互程序只会输出一种。

在样例交互器中，如果一个产品会被传送带送到某个其他桌子上时，运送这个产品的传送带是均匀随机选择的，由伪随机数决定，其结果在不同的执行中不会改变。为了改变伪随机数种子，可以用第一个整数参数运行样例交互器，如下所示。

./grade 2023

交互注意事项

对于一些组测试数据，实际的交互器是适应性的。这意味着在最初交互器不必有一个确定的答案，并且交互器根据 Query 函数先前的调用来确定响应。保证至少存在一个不会与交互器做出的所有响应矛盾的答案。

样例交互

对于如下样例

3
0 2
2 1
1 0

一个样例交互过程如下表所示

函数调用		返回值
Solve(3, [0, 2], [2, 1])
	Query([0, 0], [0, 0, 1])	[1, 0, 0]
	Query([1, 0], [1, 0, 1])	[0, 1, 1]
	Query([1, 1], [0, 0, 1])	[0, 0, 1]
	Query([0, 1], [1, 1, 1])	[1, 0, 1]
	Answer([1, 0])

对于第一次调用 Query，一个与 [1, 0, 0] 可能不同的返回值是 [0, 1, 0]。

对于第二次调用 Query，桌子 $0$ 上的产品通过传送带 $0$ 被运送到桌子 $2$，并停在那里。请注意，该产品不会通过传送带 $1$ 被运送到桌子 $1$。

注意这组样例不满足任何子任务的限制。

在「文件」页面下还有两组样例，其中 sample-02.txt 满足子任务 $1$ 的限制，sample-03.txt 满足子任务 $2$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $0\le A_i,B_i\le N-1$
• 如果我们忽略传送带的方向，每对桌子都被一系列传送带所连接

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

子任务	附加限制	分值
$1$	$N=2$	$1$
$2$	$N=30$	$14$
$3$	$N=10^5,A_i=i,B_i=i+1\ (0\le i\le N-2)$	$10$
$4$	无附加限制	$75$