Problem C
Permutations on the Road: Bob
Alice and Bob frequently take long road trips to get to various programming competitions in their area. Since everything’s bigger in the state that they live in, they have turned to playing car games to pass the time.
Alice and Bob are both computer scientists, so they quickly tired of “guess the number”, as the guesser could always identify the number using a logarthmic number of guesses. To up the challenge, they created a new game: “guess the permutation”.
A permutation of length $N$ is an arrangement of the numbers $1, \dots , N$. For a given permutation $P$, define $\text {inv}(l, r)$ to be the number of pairs $(i, j)$ with $l \leq i \leq j \leq r$ such that $P_ i > P_ j$.
When playing this game, Alice thinks of a permutation, and Bob can ask Alice the result of the function $\text {inv}$ for up to $N$ inputs.
Can you help Bob figure out Alice’s permutation $P$?
Interaction
This is an interactive problem. This means that the Alice will read your queries and respond to them while your program is running.
The first line of input contains a single integer $N$ ($1 \leq N \leq 1\, 000$), the length of the permutation.
Your program should interact with the judge by making up to $N$ queries of the form “$?\; l\; r$” (without quotes), with $1 \leq l \leq r \leq N$. Each query should be on its own line. Make sure to output a newline and flush standard out after each query.
After your program makes a query, it should read a response from standard in. This response is on its own line and is a single integer, the value $\text {inv}(l, r)$.
Once you know the permutation $P$, output a line of the form “$!\; P_1\; P_2\; \dots \; P_ N$” (without quotes). After this your program should exit. This final guess does not count toward your limit of $N$ queries.
If your program makes more than $N$ queries, it will be terminated and receive a wrong answer verdict.
Sample Interactions
|
Your output |
Kattis output |
Notes |
|
$3$ |
$N = 3$ |
|
|
$?\; 1\; 3$ |
||
|
$0$ |
$\text {inv}(1, 3) = 0$ |
|
|
$!\; 1\; 2\; 3$ |
$P = [1, 2, 3]$ |
In the first sample interaction, the permutation is $P = [1, 2, 3]$. This is the only permutation of length $3$ with $\text {inv}(1, 3) = 0$.
|
Your output |
Kattis output |
Notes |
|
$3$ |
$N = 3$ |
|
|
$?\; 1\; 2$ |
||
|
$0$ |
$\text {inv}(1, 2) = 0$ |
|
|
$?\; 1\; 3$ |
||
|
$1$ |
$\text {inv}(1, 3) = 1$ |
|
|
$!\; 1\; 3\; 2$ |
$P = [1, 3, 2]$ |
In the second sample interaction, the permutation is $P = [1, 3, 2]$. This is the only permutation of length $3$ that satisfies $\text {inv}(1, 3) = 1$ and $\text {inv}(1, 2) = 0$.
