No.3590 I Love Inversions
This is an interactive problem (your program and the judge system communicate through standard input and output).
In an ancient temple there is an "Oracle", which keeps a hidden permutation $P = (P_1, P_2, \ldots, P_N)$ of length $N$. A permutation is a sequence in which each integer from $1$ to $N$ appears exactly $1$ time.
You are trying to determine this hidden permutation by sending questions (queries) to the Oracle. In $1$ query, you specify $2$ indices $L$ and $R$ ($1 \le L \le R \le N$). The Oracle returns the inversion number of the contiguous subsequence $P[L \dots R] = (P_L, P_{L+1}, \dots, P_R)$.
Specifically, it returns the number of pairs $(i, j)$ satisfying $L \le i < j \le R$ and $P_i > P_j$.
Determine the entire hidden permutation $P$ using as few queries as possible.
Input and Output
First, the length $N$ of the permutation is given from standard input.
$N$
Then, your program can send queries to the Oracle. Print each query to standard output in the following format.
? $L$ $R$
Here, $L, R$ are the endpoints of the specified interval, and must be integers satisfying $1 \le L \le R \le N$.
After you send a query, the judge system gives the result $X$ to standard input.
$X$
- If $X \ge 0$: $X$ is the inversion number of the specified subsequence $P[L \dots R]$.
- If $X = -1$: this is given when the format of the query you sent was invalid or when the query limit was exceeded. In this case, terminate your program immediately. Otherwise, the judge result is undefined.
Once you have determined all elements of the permutation, print your answer in the following format and terminate the program normally. Printing the answer does not count as a query.
! $P_1$ $P_2$ $\cdots$ $P_N$
[Note]
Be sure to flush standard output after each output (both queries and the answer). If you do not flush, you may get TLE or WA. Print a newline at the end.
Constraints
- $1 \le N \le 50,000$
- $N$ is an integer
- The maximum number of queries you may send is $N$
Sample
Sample 1
Input
4 1 0 1 3
Output
? 1 2 ? 2 3 ? 3 4 ? 1 4 ! 3 1 4 2
This sample shows an example of the interaction when $N=4$ and the hidden permutation is $P = (3, 1, 4, 2)$. (Note that during actual execution, input and output take place interactively.)
- Send
? 1 2($L=1, R=2$). The subsequence is $(3, 1)$ and its inversion number is $1$, so1is returned. - Send
? 2 3($L=2, R=3$). The subsequence is $(1, 4)$ and its inversion number is $0$, so0is returned. - Send
? 3 4($L=3, R=4$). The subsequence is $(4, 2)$ and its inversion number is $1$, so1is returned. - Send
? 1 4($L=1, R=4$). The subsequence is $(3, 1, 4, 2)$ and the inverted pairs are the $3$ pairs $(3,1), (3,2), (4,2)$, so3is returned. - Since the permutation has been determined from the above information, print
! 3 1 4 2and terminate. The number of queries sent before the answer phase is $4$, which is at most the limit of $N$, so this is accepted.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。