L - Inversion High and Low 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 400 点

問題文

この問題はインタラクティブな問題です。

(1,2,\cdots,N) の順列を単に長さ N の順列と呼ぶことにします。
長さ N の順列 P=(P_1, P_2, \cdots, P_N) があります。
また、長さ N の 2 つの順列 P,Q に対して \mathrm{dist}(P,Q) を以下のように定義します。

  • P を Q に一致させるために必要な隣接要素の交換回数の最小値

あなたは次のような質問を 500 回 まで行うことができます。

  • 長さ N の順列 Q を 1 つ指定する。以下の規則でジャッジから文字が与えられる。

    • 質問が 1 回目であれば 「=」を出力する。
    • 前回の質問であなたが出力した順列を Q_1, 今回の質問であなたが出力した順列を Q_2 とする。
      \mathrm{dist}(P,Q_1) と \mathrm{dist}(P,Q_2) の大小関係に応じて「+」「-」「=」のいずれかを出力する。具体的には以下の通りである。
      • \mathrm{dist}(P,Q_1) < \mathrm{dist}(P,Q_2) のとき「+」
      • \mathrm{dist}(P,Q_1) > \mathrm{dist}(P,Q_2) のとき「-」
      • \mathrm{dist}(P,Q_1) = \mathrm{dist}(P,Q_2) のとき「=」

長さ N の順列 P を求めてください。
ただし、回答は質問回数に含めません。

制約

  • 2 \leq N \leq 100
  • N は整数
  • P はプログラムとジャッジの対話の開始前に決定される

入出力

この問題はインタラクティブな問題です。
まず、正整数 N が標準入力に与えられます。 

N

その後、あなたは質問を行うことが出来ます。
質問は標準出力に以下の形式で出力してください(末尾に改行を入れること)。 

? Q_1 Q_2 \dots Q_N

質問が正当な場合、その質問への答え c が標準入力から与えられます。 

c

質問の形式が間違っている・質問を規定の回数より多く行なったなどの理由から質問が不正と判定された場合、質問への答えの代わりに F が与えられます。

F

この時、提出は不正解と判定され、ジャッジプログラムが終了します。

P が分かったら、回答を標準出力に以下の形式で出力してください(末尾に改行を入れること)。 

! P_1 P_2 \dots P_N

回答を受け取った場合、答えの正誤に関わらずジャッジプログラムが終了します。

注意点

  • 出力を行うたびに標準出力をflushせよ。

入出力例

以下では N=4, P= (1,2,3,4) の場合の対話例です。

入力 出力 説明
4 まず整数 N が与えられます。
? 1 2 4 3 質問として Q=(1,2,4,3) を指定します。
= 1 回目の質問であるため、必ず = が与えられます。 このとき、 \mathrm{dist}(P,Q) = 1 です。
? 1 4 2 3 質問として Q=(1,4,2,3) を指定します。
+ このとき、 \mathrm{dist}(P,Q) = 2 です。\mathrm{dist}(P,Q_1) < \mathrm{dist}(P,Q_2) が成り立つため + が与えられます。
? 2 3 1 4 質問として Q=(2,3,1,4) を指定します。
= このとき、 \mathrm{dist}(P,Q) = 2 です。\mathrm{dist}(P,Q_1) = \mathrm{dist}(P,Q_2) が成り立つため = が与えられます。
! 1 2 3 4 P を出力します。実際に P=(1,2,3,4) であるため、AC となります。