Omkar and the Meaning of Life
Contest: Technocup 2022 - Elimination Round 1
Difficulty rating: 1800
Tags: constructive algorithms, greedy, interactive

It turns out that the meaning of life is a permutation $$$p_1, p_2, \ldots, p_n$$$ of the integers $$$1, 2, \ldots, n$$$ ($$$2 \leq n \leq 100$$$). Omkar, having created all life, knows this permutation, and will allow you to figure it out using some queries.

A query consists of an array $$$a_1, a_2, \ldots, a_n$$$ of integers between $$$1$$$ and $$$n$$$. $$$a$$$ is not required to be a permutation. Omkar will first compute the pairwise sum of $$$a$$$ and $$$p$$$, meaning that he will compute an array $$$s$$$ where $$$s_j = p_j + a_j$$$ for all $$$j = 1, 2, \ldots, n$$$. Then, he will find the smallest index $$$k$$$ such that $$$s_k$$$ occurs more than once in $$$s$$$, and answer with $$$k$$$. If there is no such index $$$k$$$, then he will answer with $$$0$$$.

You can perform at most $$$2n$$$ queries. Figure out the meaning of life $$$p$$$.

Interaction format:
Start the interaction by reading single integer $$$n$$$ ($$$2 \leq n \leq 100$$$)  — the length of the permutation $$$p$$$.

You can then make queries. A query consists of a single line "$$$? \enspace a_1 \enspace a_2 \enspace \ldots \enspace a_n$$$" ($$$1 \leq a_j \leq n$$$).

The answer to each query will be a single integer $$$k$$$ as described above ($$$0 \leq k \leq n$$$).

After making a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- see documentation for other languages.

To output your answer, print a single line "$$$! \enspace p_1 \enspace p_2 \enspace \ldots \enspace p_n$$$" then terminate.

You can make at most $$$2n$$$ queries. Outputting the answer does not count as a query.

Hack Format

To hack, first output a line containing $$$n$$$ ($$$2 \leq n \leq 100$$$), then output another line containing the hidden permutation $$$p_1, p_2, \ldots, p_n$$$ of numbers from $$$1$$$ to $$$n$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the sample, the hidden permutation $$$p$$$ is $$$[3, 2, 1, 5, 4]$$$. Three queries were made.

The first query is $$$a = [4, 4, 2, 3, 2]$$$. This yields $$$s = [3 + 4, 2 + 4, 1 + 2, 5 + 3, 4 + 2] = [7, 6, 3, 8, 6]$$$. $$$6$$$ is the only number that appears more than once, and it appears first at index $$$2$$$, making the answer to the query $$$2$$$.

The second query is $$$a = [3, 5, 1, 5, 5]$$$. This yields $$$s = [3 + 3, 2 + 5, 1 + 1, 5 + 5, 4 + 5] = [6, 7, 2, 10, 9]$$$. There are no numbers that appear more than once here, so the answer to the query is $$$0$$$.

The third query is $$$a = [5, 2, 4, 3, 1]$$$. This yields $$$s = [3 + 5, 2 + 2, 1 + 4, 5 + 3, 4 + 1] = [8, 4, 5, 8, 5]$$$. $$$5$$$ and $$$8$$$ both occur more than once here. $$$5$$$ first appears at index $$$3$$$, while $$$8$$$ first appears at index $$$1$$$, and $$$1 < 3$$$, making the answer to the query $$$1$$$.

Note that the sample is only meant to provide an example of how the interaction works; it is not guaranteed that the above queries represent a correct strategy with which to determine the answer.

Example input:
5

2

0

1

Example output:
? 4 4 2 3 2

? 3 5 1 5 5

? 5 2 4 3 1

! 3 2 1 5 4

Editorial:
Solution 1
We will determine for each $$$j$$$, the index $$$\text{next}_j$$$ such that $$$p_{\text{next}_j} = p_j + 1$$$.
For each index $$$j$$$, perform a query with all $$$1$$$s except that $$$a_j = 2$$$. If the result $$$k$$$ exists, then we should set $$$\text{next}_k = j$$$.
Also, for each index $$$j$$$, perform a query with all $$$2$$$s except that $$$a_j = 1$$$. If the result $$$k$$$ exists, then we should set $$$\text{next}_j = k$$$.
For each $$$j$$$ such that $$$p_j \neq n$$$, either $$$\text{next}_j > j$$$, in which case the first set of queries will find $$$\text{next}_j$$$, or $$$\text{next}_j < j$$$, in which case the second set of queries will find $$$\text{next}_j$$$. Therefore we will fully determine the array $$$\text{next}$$$.
To compute $$$p$$$, note that the index $$$j$$$ such that $$$p_j = 1$$$ will not appear in the array $$$\text{next}$$$. Therefore, find this $$$j$$$, and set $$$p_j = 1$$$. Then set $$$j$$$ to $$$\text{next}_j$$$, and set $$$p_j = 2$$$, and so on.
The total number of queries used is $$$2n$$$, which is exactly the limit.
Solution 2
We will first determine $$$q_j = p_j - p_n$$$ for all $$$j$$$.
For each value of $$$x$$$ from $$$-(n - 1)$$$ to $$$n - 1$$$ (these are the only possible values of $$$p_j - p_n$$$), if $$$x$$$ is nonnegative, then make a query where all of $$$a + 1$$$ is $$$x$$$ except that $$$a_n = 1$$$; otherwise, make a query where all of $$$a$$$ is $$$1$$$ except that $$$a_n = 1 - x$$$. If the result $$$k$$$ exists, then $$$q_k = x$$$.
Note that there is at most one $$$k$$$ such that $$$q_k = x$$$ for each $$$x$$$, so we will fully determine $$$q$$$ this way (obviously we need to manually set $$$q_n = 0$$$).
$$$p_n$$$ is then equal to the number of $$$j$$$ such that $$$q_j \leq 0$$$. Using this, we can determine the rest of $$$p$$$ as $$$p_j = q_j + p_n$$$.
The total number of queries used is $$$2n - 1$$$, which is $$$1$$$ below the limit.
Bonus question: Optimize this solution to use $$$n$$$ queries.