Background

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:

void answer(std::vector<int>);
int query(std::vector<int>);

Please submit in C++ 20. Passing is not guaranteed if you use other standards.

Problem Description

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<int> 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<int> 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.

Input Format

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$.

Output Format

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.

4
2 0 3 1

Hint

Below is one possible interaction process:

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