P9512 [JOI Open 2023] Ancient Machine 2 / Ancient Machine 2

**Translated from [JOI Open 2023](https://contests.ioi-jp.org/open-2023/index.html) T1 「[古代の機械 2](https://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2023/ancient2/2023-open-ancient2-statement.pdf) / [Ancient Machine 2](https://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2023/ancient2/2023-open-ancient2-statement-en.pdf)」.** **This is an interactive problem.** **Before submitting this problem, be sure to carefully read the following content.** This problem only supports C++ submissions (C++14 is recommended; please do not use C++14 (GCC9)). Due to Luogu’s special interactive mechanism, when submitting this problem, please remove the line ```#include "ancient2.h"``` from your code, and paste the following line at the very beginning of your code: ```cpp int Query(int m, std::vector a, std::vector b); ```

Bitaro and Bibako are archaeologists who excavate and investigate the ruins of the JOI Kingdom. In the ruins, Bitaro found an ancient stone tablet, and Bibako found an ancient machine. From the research results, Bitaro found that a string $S$ of length $N$ is written on the tablet. Each character of the string is either `0` or `1`. However, he still does not know what each character in $S$ is. On the other hand, from the research results, Bibako figured out how to use the machine. To use it, we need to place the tablet on the machine, input an integer $m$ and two integer sequences $a, b$, and then make one query. Here, the integer $m$ and the sequences $a, b$ must satisfy the following conditions: - The integer $m$ is between $1$ and $1\ 002$ (inclusive). - The lengths of the sequences $a$ and $b$ are both $m$. - Each element of the sequences $a, b$ is an integer between $0$ and $m-1$ (inclusive). If we place the tablet on the machine, input an integer $m$ and two integer sequences $a, b$, and then make one query, the machine will operate as follows and display an integer. 1. The machine sets its **memory area** to $0$. 2. The machine performs the following operation $N$ times. The $(i+1)$-th operation ($0 \le i \le N-1$) is performed as follows. Let $x$ be the current integer in the machine’s memory area. The machine reads the character $S_i$, where $S_i$ is the $i$-th character of the string $S$ (0-indexed). - If $S_i$ is `0`, the machine sets the memory area to $a_x$, where $a_x$ is the $x$-th element of sequence $a$ (0-indexed). - If $S_i$ is `1`, the machine sets the memory area to $b_x$, where $b_x$ is the $x$-th element of sequence $b$ (0-indexed). 3. The machine displays the integer finally stored in the memory area. Using this machine, Bitaro wants to determine the string written on the tablet. However, because the machine is very fragile, the number of queries must not exceed $1\ 000$. Also, the maximum value of the integer $m$ input to the machine should be as small as possible. Using this machine, write a program to determine the string written on the tablet. **Implementation Details** At the beginning of your program, you need to include the library `ancient2.h` using the preprocessing directive `#include`. It should implement the following function. - `std::string Solve(int N)` This function is called exactly once for each testdata. This function must return the same string as the string $S$ written on the tablet. - The parameter `N` represents the length $N$ of the string $S$ written on the tablet. - This function must return a string of length $N$. If the returned string does not have length $N$, your program will be judged **Wrong Answer [1]**. - Each character of the returned string must be either `0` or `1`. If this condition is not satisfied, your program will be judged **Wrong Answer [2]**. - The returned string must be identical to the string $S$ written on the tablet. If this condition is not satisfied, your program will be judged **Wrong Answer [3]**. Your program may call the following function. - `int Query(int m, std::vector a, std::vector b)` By using this function, your program can make one query. - The parameter `m` is the integer $m$ input to the machine. - The parameters `a` and `b` are the two integer sequences $a, b$ input to the machine. - The return value is the integer displayed by the machine at the end when we place the tablet on the machine, input the above integer and sequences, and make one query. - The parameter `m` must be between $1$ and $1\ 002$ (inclusive). If this condition is not satisfied, your program will be judged **Wrong Answer [4]**. - The lengths of sequences `a` and `b` must both be equal to $m$. If this condition is not satisfied, your program will be judged **Wrong Answer [5]**. - Each element of sequences `a` and `b` must be between $0$ and $m-1$ (inclusive). If this condition is not satisfied, your program will be judged **Wrong Answer [6]**. - The number of calls to the function `Query` must not exceed $1\ 000$. If it exceeds $1\ 000$, your program will be judged **Wrong Answer [7]**. **Notes** - Your program may implement other functions for internal use, or use global variables. - Your program is not allowed to use standard input/output. Your program is not allowed to communicate with other files in any way. However, your program may output debug information to standard error output. **Compilation and Test Run** You can download the sample grader from “Files” → “Additional Files” to test your program. The “Additional Files” also include a sample source file of your program. The sample interactor is the file `grader.cpp`. To test your program, you need to put the three files `grader.cpp`, `ancient2.cpp`, and `ancient2.h` in the same folder, and compile your program using the following command. You can also run `compile.sh` to compile your program. ```shell g++ -std=gnu++17 -O2 -o grader grader.cpp ancient2.cpp ``` When compilation succeeds, an executable file `grader` will be generated. Note that the actual interactor is different from the sample one. The sample interactor runs as a single process, meaning it reads input data from standard input and outputs results to standard output.

The first line contains an integer $N$. The second line contains a string $S$ of length $N$.

The sample interactor outputs the following content to standard output. - If your program is judged correct, it outputs the maximum value of the parameter `m` among all calls to `Query`, for example, `Accepted: 22`. However, if your program is judged correct without calling `Query`, it outputs `Accepted: 0`. - If your program is judged with any type of wrong answer, the sample interactor outputs its category, for example, `Wrong Answer [4]`. If the program satisfies multiple wrong answer categories, the sample interactor will output only one of them.

**Sample Explanation** The sample function calls are as follows. | Call to `Solve` | Return value | Call to `Query` | Return value | | :------------: | :----------: | :-------------: | :----------: | | `Solve(3)` | | | | | | | `Query(4, [3, 3, 2, 2], [2, 2, 1, 0])` | `3` | | | | `Query(2, [0, 1], [1, 0])` | `0` | | | | `Query(1, [0], [0])` | `0` | | | | `Query(3, [1, 1, 1], [1, 1, 1])` | `1` | | | `"110"` | | | Suppose the string $S$ written on the tablet is `110`. If we place the tablet on the machine, input $(m, a, b) = (4, [3, 3, 2, 2], [2, 2, 1, 0])$, and make one query, the machine will operate as follows. 1. The machine sets the memory area to $0$. 2. In the first operation, since $S_0$ is `1`, the machine sets the memory area to $b_0$, i.e. $2$. 3. In the second operation, since $S_1$ is `1`, the machine sets the memory area to $b_2$, i.e. $1$. 4. In the third operation, since $S_2$ is `0`, the machine sets the memory area to $a_1$, i.e. $3$. 5. Since the integer finally stored in the memory area is $3$, the machine displays $3$. Note that this sample input does not satisfy the constraint $N = 1\ 000$. In the files, `sample-02.txt` satisfies this constraint. **Constraints** For all testdata, the following hold: - $N = 1\ 000$ - $S$ is a string of length $N$ - Each character of $S$ is either `0` or `1` For each testdata, the actual interactor is **not** adaptive. This means the answer is already fixed when the interactor starts. If your program is judged with any type of wrong answer on any testdata, you will receive $0$ points for this problem. If your program is judged correct on all testdata, your score is determined by $M$, where $M$ is the maximum value of the parameter `m` among all calls to `Query`. However, if your program is judged correct without calling `Query`, your score is determined with $M = 0$. - If $103 \le M \le 1\ 002$, your score is $10 + \lfloor \frac{(1002 - M)^2}{9000} \rfloor$. - If $0 \le M \le 102$, you will receive $100$ points. Here, $\lfloor x \rfloor$ denotes the greatest integer not exceeding $x$. Translated by ChatGPT 5