This is an interactive problem. See the section Interaction for more details.
You are an Imperial Colonel sitting in a regular meeting with Darth Vader and the other officers. Lord Vader sighs and goes on his usual rant. "DAE (does anybody else) remember when we had clone troopers, peak fighters that literally took over the galaxy? Now our conscript stormtrooper armies are utterly insignificant next to the power of the force. They couldn't even the side of a barn with their blasters!"
You want to create an elite stormtrooper squadron to impress Lord Vader. To do this, you grab $$$n$$$ stormtroopers from across the galaxy. This new squadron will have a strict meritocratic hierarchy, but to determine this you need to order these $$$n$$$ stormtroopers from strongest to weakest. You decide to run a series of 1v1 competitions. Each day for up to $$$n$$$ days, you will pair up all of the $$$n$$$ stormtroopers into $$$\frac{n}{2}$$$ 1v1 matchups. At the end of the competition, use the results to find a definitive ranking of the $$$n$$$ stormtroopers.
It is guaranteed that no two stormtroopers have equal strength, and the strength of each stormtrooper does not change across different days. It can be assumed that a stronger stormtrooper will always win in a match against a weaker stormtrooper.
The first line contains a positive integer $$$n$$$ ($$$2 \leq n \leq 256$$$, $$$n$$$ is a power of 2) — the number of stormtroopers that need to be ordered.
You can use this website https://acpc-ucd.com/interact.html to assist in testing the interactions.
To create a new pairing, output "?" followed by a permutation of length $$$n$$$, $$$s_1, s_2, ..., s_n$$$ where each odd-indexed stormtrooper $$$s_i$$$ faces $$$s_{i + 1}$$$ during that days' practice. You can create a new set of pairings and query "?" any number of times between $$$[0, n]$$$.
After each "?" query, you must read in $$$\frac{n}{2}$$$ integers $$$w_1, w_2, ..., w_{n / 2}$$$ — the winner of each match. Winner $$$w_j$$$ corresponds to the match between $$$s_{2j-1}$$$ and $$$s_{2j}$$$. For example, $$$w_2$$$ would be the winner of the match between $$$s_3$$$ and $$$s_4$$$ for $$$n \ge 4$$$.
To give your final, definitive ordering of the strength of the stormtroopers, output "!" followed by a permutation of length $$$n$$$ representing each stormtrooper in order from strongest to weakest $$$s_1, s_2, ..., s_n$$$.
A sequence of $$$n$$$ numbers is called a permutation if it contains all integers from 1 to $$$n$$$ exactly once. For example, the sequences [3,1,4,2] and [2,1] are permutations, but [1,2,1], [0,1] and [1,3,4] — are not.
Invalid outputs will result in Wrong Answer.
Flushing the output:
After printing a query, do not forget to output the new-line character 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;
- stdout.flush() in Python;
- search the respective documentation for other languages.
Interactive Problems: Guide for Participants https://mirror.codeforces.com/blog/entry/45307
4 4 1 1 3 1 4 3 1
? 4 2 1 3
? 1 2 3 4
? 1 3 2 4
? 2 3 1 4
! 1 3 4 2In the example, "standard output" represents the user output, and "standard input" represents the interactive response to the output. Extra line spaces have been added to the example case for visual clarity.
In the first query ? 4 2 1 3, the response 4 1 indicates that stormtrooper 4 won against stormtrooper 2 and stormtrooper 1 won against stormtrooper 3.
| Name |
|---|