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

問題文

あなたはパズルゲームに夢中になっています。このステージでのあなたの任務は、宝箱を開けることです。

手元には $0 \sim n-1$ の番号が振られた $n$ 本の鍵があり、宝箱には同じく $0 \sim n-1$ の番号が振られた $n$ 個の鍵穴があります。あなたの任務は、関連する手がかりを集め、鍵を特定の順序で鍵穴に差し込み、スイッチを押して宝箱を開けることです。この正しい鍵の順序は、長さ $n$ の順列 $p$（添字は $0$ から開始）とみなすことができ、$i$ 番目の鍵穴に $p_i$ 番の鍵を入れることを意味します。

あなたの試行は、長さ $n$ の順列 $q$ を提示することとみなせます。これは、$i$ 番目の鍵穴に $q_i$ 番の鍵を入れることを意味します。すべての $0 \le i \le n-1$ について $p_i=q_i$ であれば、あなたの試行は正解であり、宝箱を開けてステージをクリアできます。そうでなければ失敗です。試行のチャンスは一度きりですので、慎重に行う必要があります。

注意深く観察した結果、宝箱の裏に隠しボタンがあることを発見しました。順列 $q$ を提示して鍵を鍵穴にセットした後、隠しボタンを押すと、宝箱は「何本の鍵が正しい位置に置かれているか」、すなわち $p_i=q_i$ を満たす $0 \le i \le n-1$ の個数を教えてくれます。この操作を1回のクエリと呼びます。最終的な開錠スイッチを押す前に、答えとなる順列 $p$ を特定するのに十分な情報を集めるまで、何度でも順列 $q$ を変更してクエリを行うことができます。

ただし、ゲームの難易度と面白さを考慮し、特別な規定があります。クエリの回数は $20000$ 回を超えてはなりません。これを超えると宝箱は永久にロックされ、ゲームオーバーとなります。ゲームを成功させられるかどうかは、あなたの腕次第です！

実装の詳細

メイン関数を実装する必要はなく、また実装すべきではありません。プログラムの先頭で #include "puzzle.h" を行い、以下の関数を実装してください。

void play(int n);

• $n$ は順列の長さを表します。
• インタラクティブライブラリの実行中、この関数はちょうど1回呼び出されます。

以下の2つの関数を呼び出すことができます。

int query(const std::vector<int> &q);

• $q$ は長さ $n$ の順列である必要があります。すなわち、$q$ の長さは $n$ であり、$0 \sim n-1$ のすべての整数が $q_0 \sim q_{n-1}$ にちょうど1回ずつ含まれている必要があります。
• この関数は、提示した順列 $q$ と答えの順列 $p$ を比較し、今回のクエリの結果、すなわち $0 \le i \le n-1$ かつ $p_i = q_i$ を満たす整数の個数を返します。
• この関数の呼び出し回数は $20000$ 回を超えてはなりません。

void check(const std::vector<int> &q);

• $q$ は長さ $n$ の順列である必要があります。すなわち、$q$ のサイズは $n$ であり、$0 \sim n-1$ のすべての整数が $q_0 \sim q_{n-1}$ にちょうど1回ずつ含まれている必要があります。
• この関数は、プログラムの play 関数実行中にちょうど1回実行される必要があります。
• この関数は、提示した順列 $q$ と答えの順列 $p$ を比較し、$p=q$ であれば正解とみなし、そうでなければ不正解とみなします。
• いずれの場合も、インタラクティブライブラリはこの関数の実行終了後、対応する情報を出力して直ちに終了します。

query または check 関数を呼び出す際、渡す引数が上記の要件を満たしていることを保証してください。

詳細な実装については、配布ファイル内の参考インタラクティブライブラリを参照してください。

テストプログラムの方法

配布ファイルには、インタラクティブライブラリの参考実装 grader.cpp が含まれています。最終的なテストで使用されるインタラクティブライブラリの実装はこれとは異なるため、選手の解法は特定のインタラクティブライブラリの実装に依存してはなりません。

ソースプログラム名を puzzle.cpp とし、配布ファイルをソースプログラムと同じディレクトリに配置した場合、以下のコマンドでコンパイルして実行ファイルを作成できます。

g++ grader.cpp puzzle.cpp -o puzzle -O2 -std=c++14 -lm

上記の方法でコンパイルされた実行ファイルを実行する場合：

• 実行ファイルは標準入力から以下の形式のデータを読み込みます。

  • 1行目：順列の長さを表す正の整数 $n$。$2 \leq n \leq 1000$ であることを保証してください。
  • 2行目：答えの順列を表す $n$ 個の整数 $p_0, p_1, \dots, p_{n-1}$。$p_0, \dots, p_{n-1}$ が長さ $n$ の順列、すなわち $0 \sim n-1$ のすべての整数がちょうど1回ずつ出現することを確認してください。

• 読み込み完了後、インタラクティブライブラリはそのデータセットを使用してテストを行い、以下の内容を出力します。

  • プログラムが正常に実行され、query 関数の呼び出し回数が $20000$ 回以下であり、かつ check 関数に正しい順列を渡した場合、以下の内容が出力されます。

    Correct.
    cnt = x

    ここで $x$ はプログラムが query 関数を呼び出した回数です。

  • そうでない場合、対応するエラーメッセージが出力されます。

入出力例

入力 1

3
1 0 2

出力 1

Correct.
cnt = 3

注記

これは配布された grader.cpp と正しく動作するソースプログラムを使用した際に得られる出力例です。

この例において、考えられる呼び出し手順は以下の通りです。

• query([0, 1, 2]) を呼び出し、$1$ が返る。
• query([0, 2, 1]) を呼び出し、$0$ が返る。
• query([1, 0, 2]) を呼び出し、$3$ が返る。
• check([1, 0, 2]) を呼び出す。

採点方法

評価時、OJ にソースプログラムを提出するだけでよく、配布された他のファイルを変更しても評価結果には影響しません。

本問題はまず伝統的な問題と同様の制限を受けます。 例えば、コンパイルエラーは全得点 $0$ 点となり、実行時エラー、時間制限超過、メモリ制限超過などは該当するテストケースが $0$ 点となります。自身で定義した変数およびインタラクティブライブラリから与えられた変数とそのメモリ空間のみにアクセスでき、それ以外の空間へのアクセスはコンパイルエラーや実行時エラーを引き起こす可能性があります。

上記の条件以外で、あるテストケースにおいてプログラムが不正な関数呼び出しを行った場合、check 関数を呼び出さなかった場合、check 関数が誤った回答をした場合、または query 関数の呼び出し回数が $20000$ 回を超えた場合、そのテストケースは $0$ 点となります。それ以外の場合、そのテストケースの得点は以下の「小課題」の記述に従います。

小課題

本問題はバンドルテストです。各小課題において、得点はその小課題に含まれるすべてのテストケースの得点の最小値となります。

すべてのテストケースにおいて、$1 \leq n \leq 1000$ です。

最初の $6$ つの小課題については、プログラムが正常に動作し、query 関数の呼び出し回数が $20000$ 回以下であり、かつ check 関数に正しい順列を渡した場合、そのテストケースの満点を得ることができます。

第 $7$ 小課題については、上記に加えて部分点を得ることができます。プログラムが query を呼び出した回数を $m$ とすると、得点は以下の通りです。

注記

合法的なデータおよび制限範囲内の呼び出しに対して、インタラクティブライブラリ自体の実行時間は $0.2\text{s}$ を超えず、使用メモリは $128\text{MiB}$ を超えないことが保証されています。

インタラクティブライブラリの正常な動作に必要なヘッダーファイルは配布された参考インタラクティブライブラリに含まれており、プログラムには必要なヘッダーファイルを含めることができます。

本問題のインタラクティブライブラリは適応型ではありません。すなわち、play 関数が呼び出される前に答えの順列は確定しており、あなたのクエリに応じて変化することはありません。

入出力ファイルへのアクセス、評価システムへの攻撃、または評価ライブラリへの攻撃などによる得点は不正行為とみなされ、無効となります。