P10642 [BalticOI 2022] Art Collection (Day1)

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: ```cpp #include void answer(std::vector); int publish(std::vector); ``` You need to implement a function `void solve(int N)`, which can call the following functions: - `int publish(std::vector 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 R)` - This function submits your answer to the interactive library, indicating the permutation you have guessed. - You must call this function exactly once.

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.

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!`.

### Sample Interaction Consider the permutation $P$ is $\{1,3,2\}$. The interaction in the sample is as follows: | Call | Return Value | Explanation | | :------------------: | :----------: | :----------------------------------: | | `publish({1, 2, 3})` | 1 | The valid ordered pair is $(3,2)$ | | `publish({2, 3, 1})` | 3 | Valid ordered pairs are $(1,3),(1,2),(3,2)$ | | `answer({1, 3, 2})` | | The answer matches the correct one | ### 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