Reconstructing the Library

Centuries passed in a blink, and JOI City is now in ruins. In the remains of its old library, the explorer IOI-chan discovered intriguing information about a horizontal bookshelf that used to hold books. The bookshelf had \(N\) positions (numbered from 0 to \(N-1\)), and there were \(N\) books (numbered from 0 to \(N-1\)). A placement is any assignment of these \(N\) books to the \(N\) positions with exactly one book per position. There is one correct placement in which the book \(b_i\) is placed at position \(i\) for each \(0 \le i \le N-1\) (with all \(b_i\)'s distinct).

The library was restored to the correct placement by repeating the following operation:

Let x be the leftmost book whose current position is different from its position in the correct placement. Let y be the book currently at x's correct position. Swap x and y.

IOI-chan cannot see the correct placement but discovered an ancient machine that can answer queries. You can submit a placement a (an array of length \(N\) representing the current arrangement, where the book a[i] is at position i) and the machine returns the number of operations needed to turn this placement into the correct placement using the above procedure.

Your task is to determine the correct placement by making no more than 5,000 queries to the machine.

Implementation Details:

• This is an interactive problem. You need to submit a single source file named library3.cpp (or its equivalent in your language).
• You must include library3.h and implement the following function:
  • void solve(int N): This function is called exactly once per test case. The parameter N represents the number of books.
• You may call the following functions:
  • int query(const std::vector<int> a): Sends a query with placement a. The machine returns an integer indicating the number of operations required to transform a into the correct placement. The array a must:
    • Have length exactly N.
    • Contain each integer from 0 to N-1 exactly once.
    • Be such that every element is in the range [0, N-1].
    Calling query more than 5,000 times will lead to Wrong Answer.
  • void answer(std::vector<int> b): Use this function to submit your final answer, where b is the correct placement (i.e. the book b[i] is at position i). You must call answer exactly once.
• You may define additional functions and use global variables if needed.
• Your solution must not perform any standard input/output operations.

Note: Although the correct placement is hidden, for the purpose of sample testing you can assume that the correct placement is the identity permutation \(\{0, 1, \ldots, N-1\}\). Your solution will be tested on multiple test cases with N varying.

Compilation command (for C++): g++ -std=gnu++20 -O2 -o grader grader.cpp library3.cpp

inputFormat

This is an interactive problem. There is no conventional input. Instead, the testing system will call the function solve(int N) with an integer N representing the number of books.

outputFormat

This is an interactive problem. There is no conventional output. Instead, your program must call the function answer(vector<int> b) (or its equivalent) exactly once, where b is the correct placement (i.e. b[i] is the book at position i in the correct placement).

sample

N = 1

Correct placement: [0]

The program should output [0] by calling answer.