Problem B
Boredom Buster
It goes like this: You have a shuffled deck of $n$ cards, where $n$ is even and each card contains a number from $1$ to $n/2$. There are exactly two cards of each number. The cards are laid face down on the table and your goal is to find what number is written on each of them. In one move, you pick up two cards. Before revealing them, you randomly shuffle them so that you do not know which card was where. Then you look at the two cards. After that, you shuffle them again face down before you put them back where they were. That way, you know the numbers of the two cards and where they are, but not which card ended up where, or even what card came from which spot initially.
Your task is to write a program that will beat this game.
Interaction
This is an interactive problem. Your submission will be run against an interactor, which reads the standard output of your submission and writes to the standard input of your submission. This interaction needs to follow a specific protocol:
-
The interactor first sends an integer $n$ ($2 \leq n \leq 10^5$, $n$ is even). The only time $n$ is not equal to $10^5$ is in the sample.
-
Your submission then repeatedly sends two integers $x$ and $y$ ($1 \leq x, y \leq n$, $x \neq y$) preceded by “?”.
-
The interactor replies with two integers $a$ and $b$ ($1 \leq a, b \leq n/2$), indicating that after the query either the $x$th card is $a$ and the $y$th card is $b$, or the $x$th card is $b$ and the $y$th card is $a$.
-
When you are ready to print the answer, print “!” followed by $n$ integers $a_1, a_2, \ldots , a_ n$, where $a_ i$ is the number of the $i$th card at the time of writing.
You may use at most $92\, 000$ moves. Printing the answer does not count as a move.
The interactor is not adaptive. Initial positions of the cards are determined by the interactor before any interaction takes place. When you make a move the two cards will be shuffled uniformly randomly by the interactor both before being shown to you and before being placed back down. The initial layout of the cards is guaranteed to be a random permutation of $1, 1, 2, 2, \dots , n/2, n/2$.
Your submission will be run on exactly $100$ test cases, each of which will have $n = 10^5$.
Make sure you flush the buffer after each write.
A testing tool is provided to help you develop your
solution.
| Read | Sample Interaction 1 | Write |
|---|
6
? 2 1
3 2
? 5 3
2 3
? 6 4
1 1
? 1 3
3 3
! 3 2 3 1 2 1
