luogu#P9512. [JOI Open 2023] 古代机器 2
[JOI Open 2023] 古代机器 2
题目背景
译自 JOI Open 2023 T1 「古代の機械 2 / Ancient Machine 2」
这是一道交互题。
在提交本题前请务必仔细阅读以下内容。
本题只支持 C++ 语言提交(建议使用 C++14,请不要使用 C++14 (GCC9))。
由于洛谷特殊的交互机制,在提交本题时,请去掉代码中的 #include "ancient2.h"
语句,并将添加以下语句粘贴到代码最开头:
int Query(int m, std::vector<int> a, std::vector<int> b);
题目描述
Bitaro 和 Bibako 是挖掘和调查 JOI 王国废墟的考古学家。在废墟中,Bitaro 发现了一块古老的石板,Bibako 发现了一台古老的机器。
从研究结果中,Bitaro 发现石板上写有一个长为 的字符串 。字符串中每个字符要么是 0
,要么是 1
。然而,他还不知道字符串 中的每个字符是什么。
另一方面,从研究结果中,Bibako 弄清了如何使用机器。为了使用它,我们需要将石板放在机器上,输入一个整数 和两个整数序列 ,然后做一次查询。这里整数 和整数序列 需满足如下条件:
- 整数 在 和 之间(包括两端)。
- 序列 和 的长度均为 。
- 序列 中的元素都是 和 之间的整数(包括两端)。
如果我们把石板放在机器上,输入一个整数 和两个整数序列 ,然后做一次查询,机器会按如下方式操作并显示一个整数。
-
机器对其内存区域置 。
-
机器进行如下的 次操作。第 次()操作按如下方式进行。
令 表示机器内存区域中当前的整数。机器读取字符 。这里, 是字符串 中的第 个字符(下标从 开始)。
- 如果 是
0
,机器会将内存区域置为 。其中 是序列 中第 个元素(下标从 开始)。 - 如果 是
1
,机器会将内存区域置为 。其中 是序列 中第 个元素(下标从 开始)。
- 如果 是
-
这个机器将展示内存区域中最终置为的整数。
使用这个机器,Bitaro 想要确定石板上写的字符串。然而,因为这个机器十分脆弱,查询的次数不能超过 。此外,输入机器的整数 的最大值需要越小越好。
使用这个机器,写一个程序确定石板上写的字符串。
【实现细节】
你需要在程序一开始使用预处理指令 #include
引入库 ancient2.h
。它应当实现如下函数。
-
std::string Solve(int N)
这个函数在每组测试数据中仅被调用一次。这个函数需要返回和石板上所写的字符串 相同的字符串。
- 参数
N
表示石板上写的字符串 的长度 。 - 这个函数需要返回一个长度为 的字符串。如果字符串长度不为 ,你的程序会被判为 Wrong Answer [1]。
- 返回值中每个字符要么是
0
,要么是1
。如果该条件不满足,你的程序会被判为 Wrong Answer [2]。 - 返回值应当与石板上写的字符串 相同。如果该条件不满足,你的程序会被判为 Wrong Answer [3]。
你的程序可以调用如下函数。
-
int Query(int m, std::vector<int> a, std::vector<int> b)
使用这个函数,你的程序可以做一次查询。
- 参数
m
是输入机器的整数 。 - 参数
a
,b
是输入机器的两个整数序列 。 - 返回值是当我们把石板放在机器上,并输入上述整数和序列,做一次查询是机器最后显示的整数。
- 参数
m
应当在 和 之间(包括两端)。如果该条件不满足,你的程序会被判为 Wrong Answer [4]。 - 序列
a
和b
的长度均应等于 。如果该条件不满足,你的程序会被判为 Wrong Answer [5]。 - 序列
a
和b
中元素均应在 和 之间(包括两端)。如果该条件不满足,你的程序会被判为 Wrong Answer [6]。 - 函数
Query
的调用次数不能超过 次。如果超过 次,你的程序会被判为 Wrong Answer [7]。
- 参数
- 参数
【注意事项】
- 你的程序可以实现其它函数供内部使用,或者使用全局变量。
- 你的程序禁止使用标准输入输出。你的程序禁止通过任何方式与其他文件通信。然而,你的程序可以将调试信息输出到标准错误输出。
【编译和测试运行】
你可以在「文件」中的「附加文件」下载样例 grader 来测试你的程序。「附加文件」中也包含一份你的程序的样例源程序。
样例交互器是文件 grader.cpp
。为了测试你的程序,你需要将 grader.cpp
,ancient2.cpp
和 ancient2.h
三个文件放在同一文件夹下,并且执行如下命令编译你的程序。你也可以运行 compile.sh
来编译你的程序。
g++ -std=gnu++17 -O2 -o grader grader.cpp ancient2.cpp
当编译成功时,会生成一个可执行文件 grader
。
请注意,实际的交互器和样例不同。样例交互器会作为单进程运行,即它会从标准输入中读取输入数据,并输出结果到标准输出。
输入格式
第一行一个整数 。
第二行一个长为 的字符串 。
输出格式
样例交互器会输出如下内容到标准输出。
- 如果你的程序被判为正确,它会输出
Query
函数中参数m
的最大值,如Accepted: 22
。然而,如果你的程序没有调用Query
函数并被判为正确,它会输出Accepted: 0
。 - 如果你的程序被判为任一类的答案错误,样例交互器会输出其类别,如
Wrong Answer [4]
。
如果程序满足多种答案错误的类别,样例交互器只会输出其中一个。
3
110
Accepted: 4
提示
【样例解释】
样例函数调用如下。
对 Solve 的调用 |
返回值 | 对 Query 的调用 |
返回值 |
---|---|---|---|
Solve(3) |
|||
Query(4, [3, 3, 2, 2], [2, 2, 1, 0]) |
3 |
||
Query(2, [0, 1], [1, 0]) |
0 |
||
Query(1, [0], [0]) |
|||
Query(3, [1, 1, 1], [1, 1, 1]) |
1 |
||
"110" |
假设写在石板上的字符串 是 110
。如果我们把石板放在机器上,输入 并做一次查询,机器将按如下方式操作。
- 机器将内存区域置为 。
- 对于第一次操作,因为 是
1
,机器会将内存区域置为 ,即 。 - 对于第二次操作,因为 是
1
,机器会将内存区域置为 ,即 。 - 对于第三次操作,因为 是
0
,机器会将内存区域置为 ,即 。 - 因为最终内存区域被置为的整数是 ,所以机器显示 。
注意这组样例输入不满足限制 。在文件中,sample-02.txt
满足这个限制。
【数据范围】
对于全部数据,满足:
- 是一个长为 的字符串
- 中的每个字符要么是
0
,要么是1
对于每组数据,实际的交互器 不是适应性的。这意味着交互器在开始时答案就已经确定了。
如果你的程序在任意一组数据上被判为任意一种答案错误,在本题你将获得 分。
如果你的程序在所有数据上都被判为正确,你的分数由 确定,其中 是所有数据的 Query
函数中参数 m
的最大值。然而,如果你的程序没有调用 Query
函数并且被判为正确,你的分数由 确定。
- 如果 ,你的得分为
- 如果 ,你将获得 分。
这里 表示不超过 的最大整数。