Sigma

Time Limit : 2 sec, Memory Limit : 131072 KB

I - σ

大きさ N の順列とは,数列 (1, 2, 3, …, N) の各要素を並べ替えたものである. 例えば (5, 2, 1, 4, 3) は大きさ 5 の順列だが,一方で (1, 5, 1, 2, 3) はそうではない.

この問題はリアクティブ方式のタスクである.あなたは応答プログラムと「順列当てゲーム」を行う. まず最初に,応答プログラムは順列 σを1つ内部で決める. 次に,あなたにはこの順列の大きさ N が伝えられる. この後,あなたは応答プログラムに何回か質問をする. そして,応答プログラムの持っている順列を特定することがあなたの目的である.

質問は次のようなものである: 大きさ N の順列 τ を1つ決め,それを応答プログラムに聞くと, 応答プログラムは数列 ai = (σ上での数字 i の位置と τ 上での数字 i の位置の距離)を計算する. その後,数列 (a1, a2, a3, …, aN) を昇順に並べて列 (b1, b2, b3, …, bN) を作り,あなたのプログラムに出力する.

例えば,σ = (5, 2, 1, 4, 3) のとき,τ = (2, 3, 1, 4, 5) を聞くと, 応答プログラムは内部で (a1, a2, a3, a4, a5) = (0, 1, 3, 0, 4) を計算し, これをソートした列 (b1, b2, b3, b4, b5) = (0, 0, 1, 3, 4) を出力する.

できるだけ少ない質問回数で順列を特定するプログラムを記せ. 採点方法については「採点方式」の項で記す.

入出力形式

まず,順列の大きさ N が入力として与えられる.

N

続いて,あなたのプログラムは何回か応答プログラムに質問をする.質問のフォーマットは以下であるとする.

? τ1 τ2 τ3τN

τi は,質問する順列の i 番目の要素の値である. このとき 1, …, τN) は大きさ N の順列になっていなければならない. すなわち,τi の値は 1 以上 N 以下ですべて相異なっていなければならない. この後,応答プログラムは質問に対する答えを出力する.

b1 b2 b3bN

このやりとりをコード上で実装する場合,C++では例えば次のようになる. 例えば順列 (5, 2, 1, 4, 3) を質問したい場合には,例えば

int tau[5] = {5, 2, 1, 4, 3};
printf("?");
for (int i=0; i<5; ++i) printf(" %d", tau[i]);
printf("\n");
fflush(stdout);

のようにする.次に

for (int i=0; i<5; ++i) scanf("%d", &b[i]);

とすると,配列 b に質問の答えが返ってくる.

何回か質問を行った後,あなたは応答プログラムの持つ順列 σ を特定する.フォーマットは以下の通りとする. (質問のときのフォーマットとほぼ同じで,先頭の ?! になっていることに注意せよ.)

! τ1 τ2 τ3τN

順列の特定を行った後,あなたのプログラムは直ちに終了しなければならない.終了しなかった場合のジャッジ結果は不定とする.

この問題ではテストデータごとに質問回数の上限値が設定されており,プログラムの行った質問の回数がその上限値を上回ると誤答と判定される.

制約

  • 1 ≤ N ≤ 400

入出力例1


プログラムの出力プログラムへの入力
5
? 2 3 1 4 5
0 0 1 3 4
? 1 2 3 4 5
0 0 2 2 4
? 5 4 3 2 1
0 2 2 2 2
? 5 2 1 4 3
0 0 0 0 0
! 5 2 1 4 3

σ = (5, 2, 1, 4, 3) である.何度か質問を行った後に列を特定している.

入出力例2

プログラムの出力プログラムへの入力
1
! 1

大きさ 1 の順列は 1 つしかないので質問をしなくても直ちに特定することができる.


Source: Kyoto University Programming Contest 2013 , Kyoto, Japan, 2013-07-06
http://www.kupc.jp/
http://kupc2013.contest.atcoder.jp/