408684: GYM103261 K Interactive Algorithm
Description
This is an interactive problem.
I have a hidden permutation $$$p_1$$$, $$$p_2$$$, ..., $$$p_n$$$. You are to guess it.
You can make some queries. In one query you tell me a permutation $$$q_1$$$, $$$q_2$$$, ..., $$$q_n$$$ of length $$$n$$$, and I reply you with similarity of permutations $$$p$$$ and $$$q$$$.
The similarity of two permutations is defined as follows. Let $$$w_1$$$, $$$w_2$$$, ..., $$$w_n$$$ be a permutation, then define $$$N(w)$$$ as the set of unordered pairs of adjacent elements in $$$w$$$. For example, $$$N([4, 1, 3, 2]) = \{\{1, 4\}, \{1, 3\}, \{2, 3\}\}$$$. This way, the similarity of $$$p$$$ and $$$q$$$ is the size of $$$N(p) \cap N(q)$$$.
You can make at most $$$25\,000$$$ queries. Note that no algorithm in the world can distinguish between $$$p$$$ and reversed $$$p$$$, so both of these permutations will be accepted as correct answer.
This time I will not mess with you and will not change the hidden permutation. Though I could. You should be thankful, really.
InputInitially you get a single line with a single integer $$$n$$$ ($$$2 \le n \le 400$$$) — the size of the hidden permutation.
OutputWhen you know the hidden permutation, print an exclamation mark "!" and then $$$n$$$ integers $$$p_1$$$, $$$p_2$$$, ..., $$$p_n$$$, or $$$p_n$$$, $$$p_{n - 1}$$$, ..., $$$p_1$$$.
This does not count towards query limit.
InteractionTo make a query, print a question mark "?" and then $$$n$$$ distinct integers $$$q_1$$$, $$$q_2$$$, ..., $$$q_n$$$ on a single line ($$$1 \le q_i \le n$$$).
In response read one integer $$$s$$$ ($$$0 \le s < n$$$) on a single line, the similarity of $$$p$$$ and $$$q$$$.
Do not forget to print end of line and flush your output after each query. You can make at most $$$25\,000$$$ queries.
ExampleInput5 1 3 4Output
? 1 2 3 4 5 ? 2 4 3 5 1 ? 3 4 2 5 1 ! 3 4 2 5 1