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 发现石板上写有一个长为 NN 的字符串 SS。字符串中每个字符要么是 0,要么是 1。然而,他还不知道字符串 SS 中的每个字符是什么。

另一方面,从研究结果中,Bibako 弄清了如何使用机器。为了使用它,我们需要将石板放在机器上,输入一个整数 mm 和两个整数序列 a,ba,b,然后做一次查询。这里整数 mm 和整数序列 a,ba,b 需满足如下条件:

  • 整数 mm111 0021\ 002 之间(包括两端)。
  • 序列 aabb 的长度均为 mm
  • 序列 a,ba,b 中的元素都是 00m1m-1 之间的整数(包括两端)。

如果我们把石板放在机器上,输入一个整数 mm 和两个整数序列 a,ba,b,然后做一次查询,机器会按如下方式操作并显示一个整数。

  1. 机器对其内存区域00

  2. 机器进行如下的 NN 次操作。第 i+1i+1 次(0iN10\le i\le N-1)操作按如下方式进行。

    xx 表示机器内存区域中当前的整数。机器读取字符 SiS_i。这里,SiS_i 是字符串 SS 中的第 ii 个字符(下标从 00 开始)。

    • 如果 SiS_i0,机器会将内存区域置为 axa_x。其中 axa_x 是序列 aa 中第 xx 个元素(下标从 00 开始)。
    • 如果 SiS_i1,机器会将内存区域置为 bxb_x。其中 bxb_x 是序列 bb 中第 xx 个元素(下标从 00 开始)。
  3. 这个机器将展示内存区域中最终置为的整数。

使用这个机器,Bitaro 想要确定石板上写的字符串。然而,因为这个机器十分脆弱,查询的次数不能超过 1 0001\ 000。此外,输入机器的整数 mm 的最大值需要越小越好。

使用这个机器,写一个程序确定石板上写的字符串。

【实现细节】

你需要在程序一开始使用预处理指令 #include 引入库 ancient2.h。它应当实现如下函数。

  • std::string Solve(int N)

    这个函数在每组测试数据中仅被调用一次。这个函数需要返回和石板上所写的字符串 SS 相同的字符串。

    • 参数 N 表示石板上写的字符串 SS 的长度 NN
    • 这个函数需要返回一个长度为 NN 的字符串。如果字符串长度不为 NN,你的程序会被判为 Wrong Answer [1]
    • 返回值中每个字符要么是 0,要么是 1。如果该条件不满足,你的程序会被判为 Wrong Answer [2]
    • 返回值应当与石板上写的字符串 SS 相同。如果该条件不满足,你的程序会被判为 Wrong Answer [3]

    你的程序可以调用如下函数。

    • int Query(int m, std::vector<int> a, std::vector<int> b)

      使用这个函数,你的程序可以做一次查询。

      • 参数 m 是输入机器的整数 mm
      • 参数 ab 是输入机器的两个整数序列 a,ba,b
      • 返回值是当我们把石板放在机器上,并输入上述整数和序列,做一次查询是机器最后显示的整数。
      • 参数 m 应当在 111 0021\ 002 之间(包括两端)。如果该条件不满足,你的程序会被判为 Wrong Answer [4]
      • 序列 ab 的长度均应等于 mm。如果该条件不满足,你的程序会被判为 Wrong Answer [5]
      • 序列 ab 中元素均应在 00m1m-1 之间(包括两端)。如果该条件不满足,你的程序会被判为 Wrong Answer [6]
      • 函数 Query 的调用次数不能超过 1 0001\ 000 次。如果超过 1 0001\ 000 次,你的程序会被判为 Wrong Answer [7]

【注意事项】

  • 你的程序可以实现其它函数供内部使用,或者使用全局变量。
  • 你的程序禁止使用标准输入输出。你的程序禁止通过任何方式与其他文件通信。然而,你的程序可以将调试信息输出到标准错误输出。

【编译和测试运行】

你可以在「文件」中的「附加文件」下载样例 grader 来测试你的程序。「附加文件」中也包含一份你的程序的样例源程序。

样例交互器是文件 grader.cpp。为了测试你的程序,你需要将 grader.cppancient2.cppancient2.h 三个文件放在同一文件夹下,并且执行如下命令编译你的程序。你也可以运行 compile.sh 来编译你的程序。

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

当编译成功时,会生成一个可执行文件 grader

请注意,实际的交互器和样例不同。样例交互器会作为单进程运行,即它会从标准输入中读取输入数据,并输出结果到标准输出。

输入格式

第一行一个整数 NN

第二行一个长为 NN 的字符串 SS

输出格式

样例交互器会输出如下内容到标准输出。

  • 如果你的程序被判为正确,它会输出 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"

假设写在石板上的字符串 SS110。如果我们把石板放在机器上,输入 (m,a,b)=(4,[3,3,2,2],[2,2,1,0])(m,a,b)=(4,[3,3,2,2],[2,2,1,0]) 并做一次查询,机器将按如下方式操作。

  1. 机器将内存区域置为 00
  2. 对于第一次操作,因为 S0S_01,机器会将内存区域置为 b0b_0,即 22
  3. 对于第二次操作,因为 S1S_11,机器会将内存区域置为 b2b_2,即 11
  4. 对于第三次操作,因为 S2S_20,机器会将内存区域置为 a1a_1,即 33
  5. 因为最终内存区域被置为的整数是 33,所以机器显示 33

注意这组样例输入不满足限制 N=1 000N=1\ 000。在文件中,sample-02.txt 满足这个限制。

【数据范围】

对于全部数据,满足:

  • N=1 000N=1\ 000
  • SS 是一个长为 NN 的字符串
  • SS 中的每个字符要么是 0,要么是 1

对于每组数据,实际的交互器 不是适应性的。这意味着交互器在开始时答案就已经确定了。

如果你的程序在任意一组数据上被判为任意一种答案错误,在本题你将获得 00 分。

如果你的程序在所有数据上都被判为正确,你的分数由 MM 确定,其中 MM 是所有数据的 Query 函数中参数 m 的最大值。然而,如果你的程序没有调用 Query 函数并且被判为正确,你的分数由 M=0M=0 确定。

  • 如果 103M1 002103\le M\le 1\ 002,你的得分为 10+(1002M)2900010+\lfloor \frac{(1002-M)^2}{9000}\rfloor
  • 如果 0M1020\le M\le 102,你将获得 100100 分。

这里 x\lfloor x\rfloor 表示不超过 xx 的最大整数。