题目描述

JOI-kun 正在玩一套电子电路装置。 该电子电路装置由 $N$ 个 AND 组件、 $N$ 个 OR 组件以及一块电路板组成。电路板由 $2N + 1$ 个开关和 $N$ 个组件槽组成，每个组件槽可以放置一个 AND 组件或一个 OR 组件。电路板根据所放置的组件和开关的状态输出 0 或 1。

电路板规格

• 每个开关被分配一个从 $0$ 到 $2N$ 的编号，每个开关都有 ON 或 OFF 两种状态。每个开关输出 0 或 1，具体规则如下。
• 每个组件槽被分配一个从 $0$ 到 $N - 1$ 的编号。每个组件槽也输出 0 或 1，具体规则如下。
• 每个开关和每个组件槽的输出按照编号从大到小的顺序确定，遵循以下规则。如果一个开关和一个组件槽具有相同的编号，则先确定组件槽的输出。
  • 对于 $j = 2N, 2N - 1, \dots, N$，开关 $j$ 的输出确定如下：
    • 如果开关 $j$ 为 OFF，则输出 0。
    • 如果开关 $j$ 为 ON，则输出 1。
  • 对于 $j = N - 1, N - 2, \dots, 0$，设组件槽 $j$ 的输出为 $x$。开关 $j$ 的输出确定如下：
    • 如果开关 $j$ 为 OFF，则输出 $x$。
    • 如果开关 $j$ 为 ON，则输出 $1 - x$。
  • 对于 $i = N - 1, N - 2, \dots, 0$，组件槽 $i$ 连接到两个开关 $U_i$ 和 $V_i$，其中 $i < U_i < V_i \le 2N$。设开关 $U_i$ 的输出为 $x$，开关 $V_i$ 的输出为 $y$。组件槽 $i$ 的输出确定如下：
    • 如果组件槽 $i$ 放置的是 AND 组件，则输出 $\min(x, y)$。
    • 如果组件槽 $i$ 放置的是 OR 组件，则输出 $\max(x, y)$。
• 对于每个 $j = 1, 2, \dots, 2N$，存在唯一的一个 $i$ ($0 \le i \le N - 1$) 使得 $U_i = j$ 或 $V_i = j$。
• 电路板的输出等于开关 0 的输出。

例如，当 $N = 3, U_0 = 1, V_0 = 2, U_1 = 3, V_1 = 4, U_2 = 5, V_2 = 6$，且组件槽 0 和 1 放置了 AND 组件，组件槽 2 放置了 OR 组件时，电路板的结构如下图所示。

（此处省略图片）

现在，JOI-kun 尝试在所有组件槽中放置 AND 组件。然而，结果发现其中混入了最多 $R$ 个 OR 组件。由于 AND 和 OR 组件看起来完全一样，必须通过电路板来区分它们。你的任务是通过进行最多 1000 次查询来确定哪些组件槽中包含 OR 组件，查询格式如下： * 你可以指示 JOI-kun 如何设置 $2N + 1$ 个开关。JOI-kun 将相应地配置开关并向你报告电路板的输出。

给定电路板的连接结构和 OR 组件数量的上限，编写一个程序，使用最多 1000 次查询确定所有 OR 组件的位置。

实现细节

你需要提交一个文件。 文件名为 circuit.cpp。该程序应使用 #include 预处理指令包含 circuit.h。 circuit.cpp 必须实现以下函数：

• std::string solve(int N, int R, std::vector<int> U, std::vector<int> V)
  • 该函数在每个测试用例中仅被调用一次。
  • 参数 $N$ 表示组件槽的数量 $N$。
  • 参数 $R$ 是 OR 组件数量的上限 $R$。
  • 参数 $U$ 和 $V$ 是长度为 $N$ 的数组，其中 $U[i]$ 和 $V[i]$ ($0 \le i \le N - 1$) 是连接到组件槽 $i$ 的开关编号 $U_i, V_i$。
  • 该函数必须返回一个长度为 $N$ 的字符串 $t$，由 '&' 和 '|' 组成，满足以下条件：
    • 对于每个 $i = 0, 1, \dots, N - 1$，如果组件槽 $i$ 包含 AND 组件，则 $t[i]$ 必须为 '&'。如果组件槽 $i$ 包含 OR 组件，则 $t[i]$ 必须为 '|'。
  • 如果返回的字符串 $t$ 长度不为 $N$，你的程序将被判为 Wrong Answer [1]。
  • 如果 $t$ 包含除 '&' 或 '|' 以外的字符，你的程序将被判为 Wrong Answer [2]。
  • 如果每个槽中实际放置的组件类型与返回的字符串 $t$ 所表示的类型不匹配，你的程序将被判为 Wrong Answer [3]。

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

• int query(std::string s)
  • 你可以使用此函数向 JOI-kun 发起查询。
  • 参数 $s$ 必须是一个长度为 $2N + 1$ 的字符串，仅由 '0' 和 '1' 组成。对于每个 $j = 0, 1, \dots, 2N$，如果 $s[j]$ 为 '0'，则开关 $j$ 设置为 OFF。如果 $s[j]$ 为 '1'，则开关 $j$ 设置为 ON。
  • 如果 $s$ 的长度不为 $2N + 1$，你的程序将被判为 Wrong Answer [4]。
  • 如果 $s$ 包含除 '0' 或 '1' 以外的字符，你的程序将被判为 Wrong Answer [5]。
  • 你调用此函数的次数不得超过 1000 次。如果调用次数超过 1000 次，你的程序将被判为 Wrong Answer [6]。
  • 此函数的返回值是设置开关后电路板的输出。

说明

• 你可以实现额外的辅助函数或声明全局变量以供内部使用。
• 你的程序不得使用标准输入/输出或任何其他文件交互。但是，你可以使用标准错误输出进行调试。

编译与执行

你可以从竞赛网页下载包含示例评测程序的压缩包。压缩包中还包含你的程序的示例源文件。 示例评测程序是 grader.cpp。要测试你的程序，请将 grader.cpp、circuit.cpp 和 circuit.h 放在同一目录下，并使用以下命令进行编译：

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

或者，你可以通过运行压缩包中包含的 compile.sh 文件来执行：

./compile.sh

如果编译成功，将生成一个名为 grader 的可执行文件。 注意，实际的评测程序与示例评测程序不同。示例评测程序将作为一个单一进程执行，它会从标准输入读取输入数据并将结果写入标准输出。

示例评测程序的输入格式

设 $T$ 为函数 solve 应该返回的长度为 $N$ 的字符串。示例评测程序从标准输入读取以下格式的输入：

$N \ R$ $U_0 \ V_0$ $U_1 \ V_1$ $\vdots$ $U_{N-1} \ V_{N-1}$ $T$

输出格式（示例评测程序）

示例评测程序将以下信息输出到标准输出（实际输出中不包含引号）： 如果你的程序被判定为正确，它会报告查询次数，例如 “Accepted: 22”。 如果你的程序被判定为任何类型的 Wrong Answer，示例评测程序会写入其类型，例如 “Wrong Answer [4]”。

示例评测程序在遇到任何不正确的情况时会立即终止执行。如果满足多个不正确条件，则仅显示其中一个。

评分说明

实际的评测程序不是自适应的；它从交互开始就有一个固定的答案。

数据范围

• $1 \le N \le 8000$。
• $1 \le R \le \min(N, 120)$。
• $i < U_i < V_i \le 2N$ ($0 \le i \le N - 1$)。
• 对于每个 $j = 1, 2, \dots, 2N$，存在唯一的一个 $i$ ($0 \le i \le N - 1$) 使得 $U_i = j$ 或 $V_i = j$。

子任务

1. (1 分) $N = 1$。
2. (4 分) $N \le 1000, R = 1$。
3. (5 分) $N \le 1000$。
4. (17 分) $U_i = i + 1, V_i = N + 1 + i$ ($0 \le i \le N - 1$), $R \le 70$。
5. (8 分) $U_i = i + 1, V_i = N + 1 + i$ ($0 \le i \le N - 1$)。
6. (23 分) $U_i = 2i + 1, V_i = 2i + 2$ ($0 \le i \le N - 1$), $R \le 70$。
7. (8 分) $U_i = 2i + 1, V_i = 2i + 2$ ($0 \le i \le N - 1$)。
8. (27 分) $R \le 70$。
9. (7 分) 无附加限制。