問題一覧 > 通常問題

No.3590 I Love Inversions

レベル : / AI推定難易度 : 1350 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 1024 MB / リアクティブ問題 (詳しくはこちら)
タグ : (AC するまで非表示) / 解いたユーザー数 34
作問者 : trqs / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 13317 / 自分の提出
問題文最終更新日: 2026-04-24 08:17:29
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 505 (順位表) の他の問題:

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.)

  1. Send ? 1 2 ($L=1, R=2$). The subsequence is $(3, 1)$ and its inversion number is $1$, so 1 is returned.
  2. Send ? 2 3 ($L=2, R=3$). The subsequence is $(1, 4)$ and its inversion number is $0$, so 0 is returned.
  3. Send ? 3 4 ($L=3, R=4$). The subsequence is $(4, 2)$ and its inversion number is $1$, so 1 is returned.
  4. 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)$, so 3 is returned.
  5. Since the permutation has been determined from the above information, print ! 3 1 4 2 and 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もしくは右上の雲マークをクリックしてアカウントを作成してください。