Problem Description

There is an unknown permutation $P$ with value range $[1,n]$. Each time, you may query a permutation $R$. The interactive library will return the number of ordered pairs $(i,j)$ such that, in permutation $P$, $i$ appears before $j$, while in permutation $R$, $i$ appears after $j$. You need to determine permutation $P$.

Implementation Details

You do not need to include the header file art.h at the beginning of your program. You only need to add the following code at the beginning:

#include <vector>
void answer(std::vector<int>);
int publish(std::vector<int>);

You need to implement a function void solve(int N), which can call the following functions:

• int publish(std::vector<int> R)
  • This function sends a query permutation $R$ to the interactive library. $R$ should be a permutation with value range $[1,n]$.
  • This function can be called at most $4000$ times.
• void answer(std::vector<int> R)
  • This function submits your answer to the interactive library, indicating the permutation you have guessed.
  • You must call this function exactly once.

Input Format

The sample interactive library reads the following data from standard input:

The first line contains an integer $n$.

The second line contains $n$ integers, where the $i$-th number denotes $P_i$.

If the input format is invalid, it is judged as Invalid input! directly.

Output Format

The sample interactive library outputs the following data to standard input:

After each time you call the public function, the interactive library will output one line describing your interaction.

When you call the answer function, the interactive library will output two lines.

The first line contains $n$ integers, representing the permutation you answered.

The second line outputs the verdict from the interactive library. If your answer is correct, it will return Correct: x published ranking(s)., where $x$ is the number of your interactions. Otherwise, it returns Wrong answer!.

Hint

Sample Interaction

Consider the permutation $P$ is $\{1,3,2\}$.

The interaction in the sample is as follows:

Constraints and Hints

• Subtask $1$ ($5$ points): $N \leq 6$
• Subtask $2$ ($15$ points): $N \leq 40$
• Subtask $3$ ($15$ points): $N \leq 250$
• Subtask $4$ ($15$ points): $N \leq 444$
• Subtask $5$ ($20$ points): $N \leq 2000$
• Subtask $6$ ($30$ points): no special constraints

For all testdata, it holds that $2 \leq N \leq 4000$.

Translated by ChatGPT 5