题目背景

这是一道交互题。

由于技术原因，本题暂不支持提交与评测。

如果您能够提供官方数据对应的 grader，请与 @RSY 联系。

题目描述

【题目描述】

In the factory of JOI Co., Ltd., there are $N$ tables, numbered from $0$ to $N - 1$. In the factory, there are $N - 1$ belt conveyors, numbered from $0$ to $N - 2$. The belt conveyor $i \ (0 \le i \le N - 2)$ connects the table $A_i$ and the table $B_i$. It transports products from one table to the other table. However, we cannot see the direction of transportation. If we ignore the directions of the belt conveyors, every pair of tables is connected by a number of belt conveyors.

IOI-kun is the director of the factory. Since he forgets the direction of transportation of every belt conveyor, he will perform the following sequential operations several times.

1. He chooses a number of belt conveyors, and reverses the directions of transportation of the chosen belt conveyors.
2. He chooses a number of tables, and puts a product on each chosen table.
3. For every table where a product is put, one of the following happens simultaneously.
   • If there is no belt conveyor transporting products from it, nothing happens.
   • If there are belt conveyors transporting products from it, the product on the table is transported by one of such belt conveyors. The product stops at the destination of the belt conveyor. The product will not move anymore.
4. IOI-kun confirms whether there are one or more products on each table. If there are products on a table, IOI-kun takes all of them.
5. For every belt conveyor whose direction is reversed in the operation 1., IOI-kun reverts its direction. Its direction becomes the original direction.

IOI-kun wants to specify the original direction of every belt conveyor by performing the above sequential operations at most $30$ times.

Write a program which, given information of the tables connected by the belt conveyors, implements IOI-kun’s strategy to specify the original direction of every belt conveyor by performing the above sequential operations at most $30$ times.

【实现细节】

You need to submit one file.

The file is conveyor.cpp. It should implement the following function. The program should include conveyor.h using the preprocessing directive #include.

In conveyor.cpp, the following function should be implemented.

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

This function is called only once for each test case.

• The parameter N is the number of tables $N$.
• The parameters A，B are arrays of length $N - 1$, describing the tables connected by the belt conveyors.

Your program can call the following function.

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

Using this function, IOI-kun performs the operations in the factory.

• The parameter x is an array of length $N - 1$. For $0 \le \texttt{i} \le N - 2$, IOI-kun reverses the direction of the belt conveyor i if x[i] = 1, and does not reverses the direction of the belt conveyor i if x[i] = 0.
• The parameter y is an array of length $$. For $0 \le \texttt{j} \le N - 1$, IOI-kun puts a product on the table j if y[j] = 1, and does not put a product on the table j if y[j] = 0.
• Let z be the return value of this function. It is an array of length $N$. For $0 \le \texttt{j} \le N - 1$, there are one or more products on the table j if z[j] = 1, and there is no product on the table j if z[j] = 0.
• The length of the array x should be equal to $N - 1$. If this condition is not satisfied, your program is judged as Wrong Answer [1].
• Every element of the array x should be 0 or 1. If this condition is not satisfied, your program is judged as Wrong Answer [2].
• The length of the array y should be equal to $N$. If this condition is not satisfied, your program is judged as Wrong Answer [3].
• Every element of the array y should be 0 or 1. If this condition is not satisfied, your program is judged as Wrong Answer [4].
• The function Query should not be called more than $30$ times. If it is called more than $30$ times, your program is judged as Wrong Answer [5].

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

Using this function, IOI-kun reports the original direction of each belt conveyor.

• The parameter a is an array of length $N - 1$. For $0 \le \texttt{i} \le N - 2$, the belt conveyor i transports products from $A_i$ to $B_i$ if a[i] = 0, and it transports products from $B_i$ to $A_i$ if a[i] = 1.
• The length of the array a should be equal to $N - 1$. If this condition is not satisfied, your program is judged as Wrong Answer [6].
• Every element of the array a should be 0 or 1. If this condition is not satisfied, your program is judged as Wrong Answer [7].
• If IOI-kun reports wrong direction of a belt conveyor, your program is judged as Wrong Answer [8].
• The function Answer should be called exactly once. If the function Answer is called more than once, your program is judged as Wrong Answer [9]. When the function Solve terminates, if the function Answer is not called, your program is judged as Wrong Answer [10].

Important Notices

• Your program can implement other functions for internal use, or use global variables.
• Your program must not use the standard input and the standard output. Your program must not communicate with other files by any methods. However, your program may output debugging information to the standard error.

【评测方式】

You can download an archive file from the contest webpage which contains the sample grader to test your program. The archive file also contains a sample source file of your program.

The sample grader is the file grader.cpp. In order to test your program, put grader.cpp, conveyor.cpp, conveyor.h in the same directory, and run the following command to compile your programs. Instead, you may run compile.sh contained in the archive file.

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

When the compilation succeeds, the executable file grader is generated.

Note that the actual grader is different from the sample grader. The sample grader will be executed as a single process, which will read input data from the standard input and write the results to the standard output.

输入格式

The sample grader reads the following data from the standard input.

$N$

$A_0 \ A_1 \ \cdots \ A_{N - 2}$

$B_0 \ B_1 \ \cdots \ B_{N - 2}$

$C_0 \ C_1 \ \cdots \ C_{N - 2}$

For $0 \le i \le N - 2$, we have $C_i = 0$ if the belt conveyor $i$ transports products from the table $A_i$ to the table $B_i$. Otherwise, we have $C_i = 1$.

输出格式

The sample grader outputs the following information to the standard output (quotes for clarity).

• If your program is judged as correct, it reports the number of function calls to Query as Accepted: 22.
• If your program is judged as any type of Wrong Answer, the sample grader writes its type as Wrong Answer [4].

If your program satisfies the conditions of several types of Wrong Answer, the sample grader reports only one of them.

In sample grader, among the belt conveyors transporting products from the table where a product is put, the belt conveyor transporting the product is chosen uniformly and randomly determined by pseudorandom numbers whose results do not change for different executions. In order to change the seed of pseudorandom numbers, run the sample grader with the first integer argument as follows.

./grader 2023

题目大意

题目描述

在 JOI 有限公司的工厂里，有 $N$ 张桌子，从 $0$ 到 $N-1$ 编号。工厂里有 $N-1$ 条皮带输送机，从 $0$ 到 $N-2$ 编号。第 $i$ 条 $(0 \le i \le N-2)$ 皮带输送机连接桌子 $A_i$ 和桌子 $B_i$。它将产品从一张桌子运输到另一张桌子。然而，我们不知道运输的方向。

IOI-kun 是工厂的经理。由于他忘记了每条皮带输送机的运输方向，他将多次按照以下顺序执行操作。

1. 选择几条输送带，并反转所选输送带的运输方向。
2. 选择几张桌子，并在每张选定的桌子上放一件商品。
3. 每当把产品放在一张桌子上时，就会发生以下情况之一。

• 如果没有输送带将产品从该桌子运走，则不会发生任何事情。
• 如果有输送带将产品从该桌子运走，则桌子上的产品将由其中一条输送带运输。产品将在输送带的目的地停止，并且产品将不再移动。

4. IOI-kun 会确认每张桌子上是否有产品。如果有产品在桌子上，IOI-kun 会把它们全部拿走。
5. 对于每个在操作 1 中改变了方向的皮带输送机，IOI-kun 都会将其方向恢复到原来的方向。IOI-kun 希望通过最多执行 $30$ 次上述顺序操作来为每个皮带输送机指定原始方向。

请编写一个程序，根据皮带输送机之间的连接表，实现 IOI-kun 的策略，以通过最多执行 $30$ 次上述顺序操作来为每个皮带输送机指定原始方向。

实现细节

你需要实现一份 C++ 程序，提交时不需要包含 conveyor.h。

你应该实现以下函数。

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

该函数仅在每个测试用例中被调用一次：

• 参数 $N$：传送带连接的桌子的数量。
• 参数 $A$ 和 $B$ 是长度为 $N - 1$ 的数组，描述由皮带输送机连接的桌子。

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

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

使用这个函数，IOI-kun 在工厂中执行操作。

• 参数 $x$ 是一个长度为 $N - 1$ 的数组。对于 $0\le i\le N - 2$，如果 $x_i = 1$，IOI-kun 将反转第 $i$ 个传送带的方向，否则不反转该传送带的方向。
• 参数 $y$ 是一个长度为 $N$ 的数组。对于 $0 \le j \le N - 1$，如果 $y_j = 1$，IOI-kun 将在第 $j$ 个桌子上放置一个产品，否则不会在该桌子上放置产品。
• 设 $z$ 是该函数的返回值。它是一个长度为 $N$ 的数组。对于 $0 \le j \le N - 1$，如果 $z_j = 1$，则第 $j$ 个桌子上有产品，如果 $z_j = 0$，则第 $j$ 个桌子上没有产品。
• 数组 $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$ 次。如果被调用次数超过 $30$ 次，您的程序将被评为 Wrong Answer[5]。

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

使用这个函数，IOI-kun 会报告每个输送带的原始方向。

• 参数 $a$ 是一个长度为 $N - 1$ 的数组。对于 $0 \le i \le N - 2$，如果 $a_i = 0$，则输送带 $i$ 将产品从 $A_i$ 运输到 $B_i$，如果 $a_i = 1$，则将产品从 $B_i$ 运输到 $A_i$。
• 数组 $a$ 的长度必须等于 $N - 1$。如果条件不满足，您的程序将被评为 Wrong Answer[6]。
• 数组 $a$ 中的每个元素都必须为 $0$ 或 $1$。如果条件不满足，您的程序将被评为 Wrong Answer[7]。
• 如果 IOI-kun 报告了输送带的错误方向，您的程序将被评为 Wrong Answer[8]。
• 函数 Answer 必须被恰好调用一次。如果函数 Answer 被调用多次，您的程序将被评为 Wrong Answer[9]。当函数 Solve 结束时，如果函数 Answer 尚未被调用，您的程序将被评为 Wrong Answer[10]。

输入格式

样例评测库将读入以下格式的数据：

N
A[0] A[1] ... A[N - 2]
B[0] B[1] ... B[N - 2]
C[0] C[1] ... C[N - 2]

对于 $0\le i\le N - 2$，如果第 $i$ 条传送带会将产品从 $A_i$ 运输至 $B_i$，那么 $C_i$ 为 $0$，否则 $C_i$ 为 $1$。

输出格式

样例评测库将以下信息输出到 stdout。

-如果你的程序被判断为正确，它报告的函数 Query 调用的数量为 Accepted: 22 。

-如果你的程序被判定为任何类型的错误答案，样例评分员将其类型写为 Wrong Answer[4]。

如果您的程序满足几种类型的错误答案的条件，则样例评测库只报告其中一种。

输入输出样例

样例 #1

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 的第一次调用，另一个可能的返回值是 [0,1,0]。

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

注意，这个示例输入不满足任何子任务的限制条件。

下发文件中，sample-02.txt 满足 Subtask $1$ 的限制条件，sample-03.txt 满足 Subtask $2$ 的限制条件。

对于某些测试用例，实际的评测程序是自适应的。这意味着评测程序在开始时没有固定的答案，并根据先前对 Query 函数的调用进行响应。

Translate by

提示

【评测程序示例】

Here is a sample input for the sample grader and corresponding function calls.

Sample Input 1:

3
0 2
2 1
1 0

Function Calls		Return Values
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])

For the first function call to Query, another possible return value is [0, 1, 0] other than [1, 0, 0].

For the second function call to Query, the product on the table $0$ is transported to the table $2$ by passing through the belt conveyor $0$, and stops there. Note that this product will not be transported to the table $1$ by passing through the belt conveyor $1$.

Note that this sample input does not satisfy the constraints of any subtask.

Among the files which can be obtained from the contest webpage, sample-02.txt satisfies the constraints of Subtask $1$, and sample-03.txt satisfies the constraints of Subtask $2$.

Notices for Grading

For some of the test cases, the actual grader is adaptive. This means the grader does not have a fixed answer in the beginning, and responds according to previous function calls to Query. It is guaranteed that there is at least one answer which does not contradict all the responses of the the grader.

【数据范围】

对于所有测试数据，满足 $0 \le A_i, B_i \le N - 1$，保证忽略所有传送带的方向后所有机器连通，保证所有输入均为整数。

子任务编号	分值	$N =$	特殊性质
$1$		$2$	无
$2$	$14$	$30$
$3$	$10$	$10 ^ 5$	$A_i = i$，$B_i = i + 1$
$4$	$75$		无