配点: 100 点
如何使用AtCoder提交
使用 C++ 时
circuit.h并实现问题陈述中指定的功能。- 不要使用标准输入/输出或文件输入/输出。
使用其他语言时
- 请按照问题文本的 JOIG 版本中的指定进行沟通。
JOI 您正在玩电子电路组。 电子电路组 N 的 您可以创建一个包含 和零件,N 的 您可以创建一个包含 或零件 和1 的 您可以创建一个包含 电路板 它由 组成。 电路板 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 关闭时, 当0 。 你只需要砍掉
- 开关 按住 j 为ON时, 对于1 。 你只需要砍掉
- j = N-1, N-2, \dots, 0 ,零件槽 j 的输出 x 当开关
输出 j 输出以下内容。
当
- 开关 按住 j 关闭时, 当x 。 你只需要砍掉
- 开关 按住 j 为ON时, 对于1-x 输出
- i = N-1, N-2, \dots, 0 ,零件槽 i 是
您也可以写 2 开关
它连接到 U_i, V_i 。在这里,U_i, V_i 是
您也可以写 i < U_i < V_i \leqq 2N 很满意。开关 U_i 的输出 x,开关
当 V_i 的输出 y 时,组件槽
当 AND 部件安装在 i 输出以下内容。
当
- 零件槽 它由 i 中时, 当 OR 部件安装在\min(x, y) 。 你只需要砍掉
- 零件槽 它由 i 中时, 关于\max(x, y) 。 你只需要砍掉
- j = 2N, 2N-1, \dots, N ,切换 j 输出以下内容。
当
- j = 1, 2, \dots, 2N ,U_i = j 或 至少 V_i = j 似乎是 i (0 \leqq i \leqq N - 1)只是 1 有两个。
- 电路板的输出是开关 相当于 0 的输出。
例如, 当分解为N = 3, U_0 = 1, V_0 = 2, U_1 = 3, V_1 = 4, U_2 = 5, V_2 = 6 ,零件槽 当AND部件、AND部件和OR部件安装在 0, 1, 2 中时,电路板如下图所示。

现在,当JOI尝试在所有零件槽中安装AND零件时,一些已安装的零件 很明显, 最大 R 個 的 OR 部分被混淆了。 由于“与”和“或”元件无法在视觉上区分,因此必须使用电路板来区分“与”和“或”元件。 你的工作是按照以下格式提出 JOI 问题。 该过程重复 1\,000 次,以确定 OR 组件安装在哪个组件插槽中。
- 你对你来说就是 JOI 指示 2N+1 开关的状态。 JOI按照指示改变开关的状态并告诉你电路板的输出。
给定电路板上的电路连接信息以及安装的OR组件数量的上限,1\,000 使用以下问题编写一个程序来识别 OR 组件安装在哪个组件插槽中。
实施细节
你 1 您必须提交两个文件。
您提交的文件是
名称是 circuit.cpp 。
那个程序是 #include 通过预处理器指令
加载 circuit.h 。
circuit.cpp 必须实现以下功能。
std::string solve(int N, int R, std::vector<int> U, std::vector<int> V)- 此功能 仅调用了 1 次。
- 引数
N是组件插槽的数量 N 。 - 引数
R是安装的 OR 部件数量的上限 R 。 - 引数
U,V是长度 N 数组,U[i],V[i](0 \leqq i \leqq N - 1) 是组件槽 连接到 i 的开关数量 U_{i}, V_{i} 。 - 该函数满足以下条件:
长度由
&和 按字典顺序比较|组成的长度 要变为 N 的字符串 t 。- 各 i = 0, 1, \dots, N-1 ,零件槽 i 中的部件是 AND 部件
t[i]是 您也可以写&,如果它是 OR 部分t[i]是 您也可以写|。
- 各 i = 0, 1, \dots, N-1 ,零件槽 i 中的部件是 AND 部件
- 返回值 t 的长度是 N ,不正解[1] 已确定。 调用
- 返回值 t 至
该值是
&但是|,不正解[2] 已确定。 调用 - 每个组件槽中实际安装的组件类型是返回值。 如果与 t 所代表的不同,不正解[3] 已确定。 调用
您的程序可以调用以下函数。
int query(std::string s)- 您可以使用此功能向 JOI 提问。 必须是字符串
- 引数
s是 您也可以写0和 按字典顺序比较1组成的长度 要变为 2N + 1 。每个 j = 0, 1, \dots, 2N ,s[j]是 在0然后切换 关闭 j 关闭s[j]是 在1然后切换 关闭 j 。 - 引数
s的长度是 2N+1 ,不正解[4] 已确定。 调用 - 引数
s至 该值是0但是1,不正解[5] 已确定。 调用 - 此功能 调用次数不得超过 1\,000 次。 如果调用次数超过1\,000 次,不正解[6] 已确定。 调用
- 该函数的返回值是参数
这是开关状态更改时电路板的输出,如
s所示。
重要说明
- 您可以自由地实现其他函数并声明全局变量以供内部使用。
- 您提交的程序不得以任何方式与标准输入、标准输出或其他文件交互。但是,允许将调试信息等输出到标准错误输出。
如何编译执行
用于测试创建的程序的评分程序示例是 它包含在可以从竞赛网站下载的存档中。 该存档还包含必须提交的示例文件。
评分程序的示例是 1 由两个文件组成。
该文件是 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
评分程序的示例输出
示例评分程序将以下信息输出到标准输出。
- 如果正确,则函数
呼叫
query的次数是 如果不是Accepted: 22。 - 如果答案不正确,则错误答案的类型为
Wrong Answer [4]。
当满足任何错误答案条件时,示例评分程序将结束执行。 如果要执行的程序满足多个错误答案条件,则显示的错误答案类型将是其中之一。 1 只有一个。
评分注意事项
实际评分程序不是自适应的,而是从交互开始就有固定的答案。
制約
- 1 \leqq N \leqq 8\,000.
- 1 \leqq R \leqq \min(N, 120).
- i < U_i < V_i \leqq 2N (0 \leqq i \leqq N - 1).
- j = 1, 2, \dots, 2N ,U_i = j 或 至少 V_i = j 似乎是 i (0 \leqq i \leqq N - 1)只是 1 有两个。
小課題
- (1 点) N = 1.
- (4 点) N \leqq 1\,000,R = 1.
- (5 点) N \leqq 1\,000.
- (17 点) U_i = i + 1,V_i = N + 1 + i (0 \leqq i \leqq N - 1),R \leqq 70.
- (8 点) U_i = i + 1,V_i = N + 1 + i (0 \leqq i \leqq N - 1).
- (23 点) U_i = 2i + 1,V_i = 2i + 2 (0 \leqq i \leqq N - 1),R \leqq 70.
- (8 点) U_i = 2i + 1,V_i = 2i + 2 (0 \leqq i \leqq N - 1).
- (27 点) R \leqq 70.
- (7 点)没有额外的限制。
交互示例
下面是示例评分程序读取的输入示例以及相应函数调用的示例。
入力例 1
1 1 1 2 |

1 第 query 的调用,电路板的输出可以计算如下。
- 开关 按住 1, 2 的状态分别为 ON 和 OFF,因此开关 1, 2 分别是 它总是能被 1, 0 。 你只需要砍掉
- 零件槽 它由 0 安装了 OR 部件,并连接了开关 输出 1, 2 分别是 它总是能被 1, 0 ,因此组件槽 0 是 您也可以写 \max(1, 0) = 1 。 你只需要砍掉
- 开关 按住 0 的状态为OFF,组件槽为 0 的输出是 1 ,所以切换 0 的输出是 1 。
- 因此,电路板的输出为 1 。
此输入示例满足所有子任务约束。
入力例 2
3 3 1 2 3 4 5 6 &&|

问题文本中的图表代表此输入示例的电路板。
此输入示例是一个小作业。 3, 6, 7, 8, 9 满足约束。
在可以从竞赛网站下载的文件中,sample-01-in.txt 是一个输入示例
对应于 1 ,
对应于sample-02-in.txt 是一个输入示例
对应于 2 。
另外,sample-03-in.txt 是一个小作业 3, 4, 5, 8, 9 满足约束,sample-04-in.txt 是一个小作业 3, 6, 7, 8, 9 满足约束。