Find the Permutation

There is a hidden permutation$^{1}$ $P = [P_1, P_2, \ldots, P_N]$ of the numbers $1, 2, \ldots, N$.

You can ask questions in the form $(i, j)$ with $1 \leq i, j \leq N$. Note that $i$ and $j$ does not have to be distinct.

The evaluator responds with the most significant bit of the bitwise AND$^{2}$ of $P_i$ and $P_j$. Here, the most significant bit of a number $x$ is the exponent of the highest power of $2$ that appears when writing $x$ in base $2$. For example, the most significant bit of $5 = 101_{(2)}$ is $2$, since $2^2$ appears in the binary representation of $5$. If the bitwise AND of $P_i$ and $P_j$ is $0$, the evaluator responds with $-1$.

Task

Your task is to determine the hidden permutation of at most $1\ 000$ numbers by asking no more than $30 \ 000$ questions.

Interaction protocol

Firstly, you need to include the definitions of the functions which you will use/implement in your program; use #include "find-the-permutation.h".

Please note, you don't need to write any main function. You instead need to implement the following function:

vector<int> solve(int N);

This function will be called a single time by the jury throught the execution of the program.
This function will return the hidden permutation, indexed from 1 (the vector starts with index $0$ which is meaningless; the permutation is contained between indexes $1$ and $N$).

You can ask questions by using this function:

int ask(int i, int j);

where $i$ and $j$ describe the question $(i, j)$.

For each question, if $i$ and $j$ are between $1$ and $N$ (inclusive) and the solution has not asked more than $30 \ 000$ questions, you receive the answer.

Otherwise, you receive $-100$ and the evaluator terminates the interaction immediately with an "Wrong answer" verdict.

Once found, you have to provide the hidden permutation to the jury by returning it in the previously described manner.

Constraints and clarifications

• $1 \le N \le 1 \ 000$
• The evaluator is not adaptive, meaning that in each test, the hidden permutation is fixed before your program asks any questions.
• Let $Q$ denote the number of questions asked by your program in a test case. Then, your score for this test case is calculated in the following way:
  • If $Q > 30 \ 000$ you will get $0\%$ of the points for the test;
  • If $25 \ 000 < Q \leq 30 \ 000$ you will get $20\%$ of the points for the test;
  • If $20 \ 000 < Q \leq 25 \ 000$ you will get $40\%$ of the points for the test;
  • If $15 \ 000 < Q \leq 20 \ 000$ you will get $60\%$ of the points for the test;
  • If $Q \leq 15 \ 000$ you will get $100\%$ of the points for the test.
• $^{1}$A permutation of the numbers $1, 2, \ldots, N$ is a sequence of length $N$ consisting of the numbers $1, 2, \ldots, N$, containing each number exactly once.
• $^{2}$The bitwise AND of two numbers $x$ and $y$ is the number that contains the common bits of $x$ and $y$. For example, if $x=11 = 1011_{(2)}$ and $y=13 = 1101_{(2)}$, then their bitwise AND will be $9 = 1001_{(2)}$.

Example

vector<int> solve(int N) // suppose N = 5
{
   ask(1, 5); // 2
   ask(2, 3); // 1
   ask(4, 3); // -1
   ask(4, 4); // 0
   return vector<int>{-100, 4, 3, 2, 1, 5};
}

Explanation

Suppose that the hidden permutation is $P = [4,3,2,1,5]$.

The first question asks the most significant bit of the numbers $P_1 = 4$ and $P_5 = 5$, which is $2$.

The second one asks about the hidden numbers $3$ and $2$, for which the answer is $1$.

The bitwise AND of numbers $2$ and $1$ is $0$ and thus, the answer for the third question will be $-1$.

Lastly, the answer to the fourth question is $0$, because the bitwise AND of $1$ and $1$ is $1$.

Note that this is just a sample interaction to showcase the process of asking questions, receiving answers, and guessing the hidden permutation. It does not necessarily represent an approach to finding the hidden permutation.