mouse

Once upon a time, a special mouse tried to discover a secret permutation $p_1, \dots, p_n$. However, he wasn’t able to without using a special device called the “permutation discoverer”. Given some permutation $q_1, \dots q_n$, this device tells him the number of positions $i$ for which $p_i = q_i$. He cannot use the device more than a certain number of times though.

More formally, there exists a secret permutation $p_1, \dots p_n$. You can use an operation $query(q_1, \dots q_n)$ that returns the number of positions i for which $p_i = q_i$.

Task

Given $N$, using a small enough number of queries, find $p$.

Interaction

This is an interactive problem. The contestant must implement a function void solve(int N) that eventually finds the hidden permutation p. To do this, include the header grader.h, and use the function int query(vector<int> q). If given a permutation $q$, this function will implement the behavior described earlier. To answer, do a query with a $q$ equal to what you think $p$ is. If you are correct, the return value will, of course, be N. You must terminate the solve function after receiving a result from query equal to N.

Constraints

Scoring

Let $Q$ be the number of queries used in a test. Then the scoring is as follows:

For subtask 1:

• if $Q \leq 50$, $13$ points;
• if $50 < Q \leq 200$, $9$ points;
• if $200 < Q \leq 5 \ 040$, $6$ points;
• if $Q > 5 \ 040$, $0$ points.

For subtask 2: let $Q \rq = (\lfloor Q / 100 \rfloor + 1) * 100$

• if $Q \rq \leq 400$, then $38$ points;
• if $400 < Q \rq \leq 700$, then $(38-29) \cdot (700-Q \rq) / (700-400) + 29$ points;
• if $700 < Q \rq \leq 1 \ 300$ then $(29-21) \cdot (1 \ 300-Q \rq) / (1 \ 300-700) + 21$ points;
• if $1 \ 300 < Q \rq \leq 10 \ 000$ then $(21-4) \cdot (10 \ 000-Q \rq) / (10 \ 000-1 \ 300) + 4$ points;
• If $10 \ 000 < Q \rq$, then $0$ points.

For subtask 3: define $Q \rq$ as in subtask 2

• if $Q \rq \leq 2 \ 400$, then $49$ points.
• if $2 \ 400 < Q \rq \leq 5 \ 000$, then $(49 - 29) * (5 \ 000 - Q \rq) / (5 \ 000 - 2 \ 400) + 29$
• if $5 \ 000 < Q \rq$, then $0$

NOTE: If the correct permutation is found after too many queries, you will get the verdict “Correct”, with detail “Too many queries”, and $0$ points.