P10628 [JOI Open 2024] Library 3 / Library 3

Due to limitations of the Luogu judging system, in actual submission you do not need to include $\texttt{library3.h}$. You need to add the following to your code: ```cpp void answer(std::vector); int query(std::vector); ``` Please submit in C++ 20. Passing is not guaranteed if you use other standards.

In the blink of an eye, hundreds of years have passed, and JOI City has already become ruins. IOI-chan, an explorer, is exploring the former site of the library. From the exploration results, it is known that: - In the library of JOI City, there is a horizontal bookshelf with $N$ **positions** for placing books, numbered from left to right as $0 \sim N-1$. Each position can hold only one book. - There are $N$ books on the shelf, numbered $0 \sim N-1$. - A **placement** of the $N$ books is a way to place the $N$ books into the $N$ positions. - There exists a **correct placement** of the $N$ books, in which book $B_i$ ($0 \le i \le N-1$) is placed at position $i$, and all $B_i$ are pairwise distinct. The placement of books keeps changing, and the library restores the books to the correct placement by repeatedly performing the following step: > **Operation** Let $x$ be the leftmost book such that the position of $x$ is different from its position in the correct placement. Let $y$ be the book currently at the correct position of $x$. Swap $x$ and $y$. Although IOI-chan found many old books, she cannot know the correct placement. However, she found an old machine that can perform the operation above. If she specifies a placement and queries the machine, the machine will answer how many times the operation must be repeated to go from the current placement to the correct placement. IOI-chan wants to use this machine to obtain the correct placement. Since the machine is too old, she can make at most $5\,000$ queries. You need to write a program. Given the bookshelf information, find the correct placement using at most $5\,000$ queries. [Implementation Details] **This is an interactive problem. You only need to submit one file (`library3.cpp`).** You need to include `library3.h` in the file and implement the following function: - `void solve(int N)` This function is called exactly once for each test case. - The parameter $N$ represents the number of books. In `library3.cpp`, you can call the following functions: - `int query(const std::vector a)` IOI-chan uses this function to query the machine. - The parameter `a` is an array of length $N$, i.e., the placement to be queried. That is, in the specified placement, book `a[i]` ($0 \le i \le N-1$) is placed at position $i$. - The return value is an integer, i.e., how many times the operation must be repeated to restore the specified placement to the correct placement. - In the parameter, the length of array `a` must be $N$. If this condition is not satisfied, your program will be judged **Wrong Answer[1]**. - In the parameter, every element of array `a` must be between $0$ and $N-1$. If this condition is not satisfied, your program will be judged **Wrong Answer[2]**. - In the parameter, the elements of array `a` must be pairwise distinct. If this condition is not satisfied, your program will be judged **Wrong Answer[3]**. - This function can be called at most $5\,000$ times. If the call limit is exceeded, your program will be judged **Wrong Answer[4]**. - `void answer(std::vector b)` Your program uses this function to report the correct placement. - The parameter `b` is an array of length $N$, i.e., the correct placement. That is, in the correct placement, book `b[i]` ($0 \le i \le N-1$) is placed at position $i$. - In the parameter, the length of array `b` must be $N$. If this condition is not satisfied, your program will be judged **Wrong Answer[5]**. - In the parameter, every element of array `b` must be between $0$ and $N-1$. If this condition is not satisfied, your program will be judged **Wrong Answer[6]**. - In the parameter, the elements of array `b` must be pairwise distinct. If this condition is not satisfied, your program will be judged **Wrong Answer[7]**. - If the placement you report is not the correct placement, your program will be judged **Wrong Answer[8]**. - This function must be called exactly once. If the call limit is exceeded, your program will be judged **Wrong Answer[9]**. If it is not called, your program will be judged **Wrong Answer[10]**. [Notes] Your program may define other functions and may use global variables. Your program must not use standard input/output streams, and must not read or write any other files in any form. However, your program may output debug information to the standard error stream. [Compile and Run] You can obtain the sample grader from the attachments. The sample grader is the file `grader.cpp`. Put `grader.cpp`, `library3.cpp`, and `library3.h` in the same directory, and compile your program using the following command. You may also run `compile.sh` to compile. > Compilation command: `g++ -std=gnu++20 -O2 -o grader grader.cpp library3.cpp` If compilation succeeds, an executable file `grader` will be generated. Note that the grader used in actual judging is different from the sample grader. The sample grader runs in a single process, reads input from standard input, and outputs results to standard output. *Contest announcement: The sample grader is non-adaptive. Whether the grader used in actual judging is adaptive is unknown.

The sample grader reads input in the following format: > $N$ > $B_0$ $B_1$ $\cdots$ $B_{N-1}$ In the correct placement, book $B_i$ ($0 \le i \le N-1$) is placed at position $i$.

The sample grader outputs the following result: - If your program is judged correct, it outputs the number of calls to the `query` function. For example: `Accepted: 3000`. - Otherwise, if your program satisfies any type of error, it outputs the error type as described in the statement. For example: `Wrong Answer[3]`. If your program satisfies multiple error conditions at the same time, only one error will be output.

Below is one possible interaction process: | Call | Call | Return value | | :--: | :--:| :--: | | `solve(4)` | | | | | `query([0, 1, 2, 3])` | `3` | | | `query([1, 3, 0, 2])` | `2` | | | `query([3, 0, 1, 2])` | `2` | | | `query([2, 0, 3, 1])` | `0` | | | `answer([2, 0, 3, 1])` | | Consider calling `query([0, 1, 2, 3])`. The operations will be performed as follows: - Swap the positions of book $0$ and book $1$. Then books $1,0,2,3$ are placed at positions $0,1,2,3$, respectively. - Swap the positions of book $1$ and book $3$. Then books $3,0,2,1$ are placed at positions $0,1,2,3$, respectively. - Swap the positions of book $3$ and book $2$. Then books $2,0,3,1$ are placed at positions $0,1,2,3$, respectively. After $3$ operations, the specified placement is restored to the correct placement, so the return value is `3`. The sample satisfies the constraints of all subtasks. ### Constraints - $2 \le N \le 500$. - $0 \le B_i \le N - 1$ ($0 \le i \le N - 1$). - $B_i \neq B_j$ ($0 \le i < j \le N - 1$). - All input numbers are integers. ### Subtasks 1. ($2$ points) $N \le 6$. 2. ($19$ points) $N \le 100$. 3. ($79$ points) No additional constraints. Translated by Starrykiller from the English statement. Translated by ChatGPT 5