Problem I
Olympic Ceremony
There are $N$ Olympic athletes in line for the opening ceremony of the Piltover Olympic Games. The $i$-th athlete in line belongs to some district $D_i$ in Piltover, but the organizers forgot to tell you which district each athlete belongs to. Even worse, the ceremony is about to begin, and the athletes will have no one to talk to if they aren’t with fellow athletes from their district. To make all the athletes feel more comfortable, you want all the athletes from a given district to be together in line. Additionally, even though you don’t have the list of athletes’ districts, you have a device to communicate with the organizers and learn information about the athletes’ districts. Can you find a permutation of the athletes that makes the athletes comfortable in time for the start of the ceremony?
Input
The only line of input is an integer $N \: (1 \leq N \leq 1\, 000)$, where $N$ represents the number of Olympic athletes.
Interaction
This is an interactive problem. You can interact with the
Olympic organizers using standard input and output, but you
only have time to ask $10\,
000$ questions before the ceremony begins.
To ask a question, write to standard output in the following
format:
-
“? $l$ $r$” ($1 \le l \le r \le N$) — How many unique values are in the list $D_l, \ldots , D_r$? The organizers will respond with “! $k$” to tell you that there are $k$ unique values. They have a bad habit of adding “!” before each of their answers that they won’t fix no matter how much you bug them.
To submit the desired permutation of athletes, write to standard output in the following format:
-
“! $P_1, \ldots , P_N$” ($1 \le P_i \le N$ and all $P_i$ distinct) — Athlete $P_i$ should be in the $i$-th position, and athletes from the same district should be together. More precisely, for every $1 \le i \le j \le k \le N$, if $D_{P_i} = D_{P_k}$, then $D_{P_i} = D_{P_j}$.
There may be multiple permutatations that satisfy the above.
You may output any one of them.
The judge is not adaptive, meaning that the values
$D_1,\ldots ,D_N$ for a
given test case are known to the judge before the participant
starts to query.
The total number of queries allowed is $10^4$, meaning that your program can
only output $10^4$ lines
starting with ?. In particular, the
final answer does not count as a query. If the number of
queries is exceeded, you will receive a verdict of Wrong Answer.
Any queries not in the specified form will immediately result
in a verdict of Wrong Answer. After
printing a query do not forget to output the end of line and
flush the output. Otherwise, you may receive a verdict of
Idleness limit exceeded. To do this,
use
-
fflush(stdout) or cout.flush() in C++;
-
System.out.flush() in Java;
-
stdout.flush() in Python;
-
see documentation for other languages.
| Read | Sample Interaction 1 | Write |
|---|
3
? 2 3
! 1
! 3 2 1
