P9332 [JOIST 2023] 传送带 / Belt Conveyor

不要 $\texttt{\#include "conveyor.h"}$。请使用 $\texttt{C++\,20}$ 提交。 提交前请将以下内容粘贴到代码前面： ```cpp #include void Solve(int N, std::vector A, std::vector B); std::vector Query(std::vector x, std::vector y); void Answer(std::vector a); ```

在 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`。 你应该实现以下函数。 ```cpp void Solve(int N, std::vector A, std::vector B) ``` 该函数仅在每个测试用例中被调用一次： - 参数 $N$：传送带连接的桌子的数量。 - 参数 $A$ 和 $B$ 是长度为 $N - 1$ 的数组，描述由皮带输送机连接的桌子。 您的程序可以调用以下函数： ```cpp std::vector Query(std::vector x, std::vector 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]`。 ```cpp void Answer(std::vector 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 ```plain 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` 函数的调用进行响应。 **【数据范围】** 对于所有测试数据，满足 $0 \le A_i, B_i \le N - 1$，保证忽略所有传送带的方向后所有机器连通，保证所有输入均为整数。 |子任务编号|分值|$N =$|特殊性质| |:-:|:-:|:-:|:-:| |$1$|$1$|$2$|无| |$2$|$14$|$30$|无| |$3$|$10$|$10 ^ 5$|$A_i = i$，$B_i = i + 1$| |$4$|$75$|$10 ^ 5$|无| Translate by @[tbdsh](/user/752485).