No.3590 I Love Inversions
タグ : / 解いたユーザー数 28
作問者 :
trqs
/ テスター :
p-adic
これはインタラクティブな問題（あなたの作成したプログラムとジャッジシステムが標準入出力を介して対話を行う形式）です。
古代の神殿には「神託（Oracle）」が存在し、長さ $N$ の順列 $P = (P_1, P_2, \ldots, P_N)$ を隠し持っています。順列とは、$1$ から $N$ までの整数がそれぞれちょうど $1$ 回ずつ現れる数列のことです。
あなたは神託に質問（クエリ）を送ることで、この隠された順列を特定しようとしています。 $1$ 回のクエリで、あなたは $2$ つのインデックス $L$ と $R$ ($1 \le L \le R \le N$) を指定します。神託は、連続する部分列 $P[L \dots R] = (P_L, P_{L+1}, \dots, P_R)$ に含まれる転倒数を返します。
具体的には、$L \le i < j \le R$ かつ $P_i > P_j$ を満たす組 $(i, j)$ の個数を返します。
できるだけ少ないクエリ回数で、隠された順列 $P$ を全て特定してください。
入出力
最初に、順列の長さ $N$ が標準入力から与えられます。
$N$
続いて、あなたのプログラムは神託にクエリを送信することができます。クエリは以下の形式で標準出力に出力してください。
? $L$ $R$
ここで、$L, R$ はそれぞれ指定する区間の端点であり、$1 \le L \le R \le N$ を満たす整数でなければなりません。
クエリを送信した後、ジャッジシステムから結果 $X$ が標準入力に与えられます。
$X$
- $X \ge 0$ のとき：$X$ は指定した部分列 $P[L \dots R]$ における転倒数です。
- $X = -1$ のとき：送信したクエリの形式が間違っていた場合や、クエリ制限回数を超過した場合に与えられます。この場合、プログラムを直ちに終了させてください。そうしない場合のジャッジ結果は不定です。
順列のすべての要素が特定できた場合、以下の形式で解答を出力し、プログラムを正常終了させてください。解答の出力はクエリ回数にカウントされません。
! $P_1$ $P_2$ $\cdots$ $P_N$
【注意】
各出力（クエリおよび解答）の後には必ず標準出力をフラッシュ (flush) してください。フラッシュしない場合、TLE や WA となる可能性があります。最後に改行してください。
制約
- $1 \le N \le 50,000$
- $N$ は整数である
- クエリ送信回数の上限は $N$ 回
サンプル
サンプル1
入力
4 1 0 1 3
出力
? 1 2 ? 2 3 ? 3 4 ? 1 4 ! 3 1 4 2
このサンプルは、$N=4$ で、隠された順列が $P = (3, 1, 4, 2)$ である場合のやり取りの例を示しています。（※実際の実行時には、入力と出力が対話的に行われます）
? 1 2（$L=1, R=2$）を送信。部分列は $(3, 1)$ であり、転倒数は $1$ なので1が返ります。? 2 3（$L=2, R=3$）を送信。部分列は $(1, 4)$ であり、転倒数は $0$ なので0が返ります。? 3 4（$L=3, R=4$）を送信。部分列は $(4, 2)$ であり、転倒数は $1$ なので1が返ります。? 1 4（$L=1, R=4$）を送信。部分列は $(3, 1, 4, 2)$ であり、転倒の組は $(3,1), (3,2), (4,2)$ の $3$ つなので3が返ります。- 以上の情報から順列が特定できたため、
! 3 1 4 2を出力して終了します。解答フェーズの前に送ったクエリは $4$ 回であり、上限である $N$ 回以下のため正答となります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。