これはインタラクティブ問題です。
AliceとBobは数当てゲームをしています。まず、Aliceは $b\in\{0,1\}$ を選択しますが、Bobは $b$ の値を知りません。その後、Aliceは以下の手順で $\{0,1\}^{64}$ 上の置換 $P$ を生成します。
- $b=0$ の場合、$P$ は $\{0,1\}^{64}$ 上のすべての置換の中から一様ランダムに選ばれます。
- $b=1$ の場合：
- $f_1,f_2,f_3$ はそれぞれ $\{0,1\}^{32}\to\{0,1\}^{32}$ のすべての関数の中から独立に一様ランダムに選ばれます。
- $P(x)$ を計算するために、Aliceはまず $x$ を $x=x_0\circ x_1$ と分割します（$x_0, x_1$ はそれぞれ32ビット）。
- Aliceは以下の計算を行います：
- $x_2=x_0\oplus f_1(x_1)$
- $x_3=x_1\oplus f_2(x_2)$
- $x_4=x_2\oplus f_3(x_3)$
- Aliceは $x_3\circ x_4$ を $P(x)$ の出力とします。言い換えると、$P(x_0\circ x_1)=x_3\circ x_4$ であり、$x_3, x_4$ は上記のように定義されます。
どちらの場合も、$P$ が適切に定義された置換であることは容易にわかります。今、Bobは $b$ の値を特定する必要があります。BobはAliceに対して以下の2種類のクエリを行うことができます：
- 任意の $x\in\{0,1\}^{64}$ を選び、$P(x)$ を問い合わせる。
- 任意の $x\in\{0,1\}^{64}$ を選び、$P^{-1}(x)$ を問い合わせる。
Aliceは締め切りに追われているため、Bobが行えるクエリの回数を $256$ 回以下に制限しています。しかし、Bobはランダム化の問題を扱うのが苦手なため、あなたに助けを求めています。Bobが $b$ を正しく推測するためのアルゴリズムを設計してください。
インタラクション
本問題は c++ のみをサポートしています。提出するソースファイルには interaction.h（配布ファイルを参照）をインクルードしてください。インタラクションに使用するインターフェース関数は以下の通りです：
/**
* @brief Queries P(x) or P^{-1}(x)
* @param x The value to query
* @param rev Set rev=0 to query P(x), rev=1 to query P^{-1}(x)
* @return P(x) for rev=0, P^{-1}(x) for rev=1
*/
unsigned long long getperm(unsigned long long x,int rev);
/**
* @brief Make no more than 256 calls to getperm, to guess b
* @see getperm
* @return The b you guesses
*/
int guessb();ソースファイル内で int guessb() を実装してください。この関数は getperm を $256$ 回以内で呼び出し、$b$ の推測結果として $0$ または $1$ を返す必要があります。不明な点がある場合は、配布ファイルに含まれる permutation.cpp が簡易的な実装例となっているため、それを基に修正してください。
コンパイルと実行
以下のコマンドでソースファイルとインタラクションライブラリをコンパイルし、実行ファイル grader を生成します。ここで permutation.cpp はあなたのソースファイル名です。
g++ -o grader grader.cpp permutation.cppその後、Linux/MacOSでは以下のコマンドで実行します：
./graderWindowsでは grader.exe を実行してください。
入力
各テストケースには複数のデータセットが含まれます。
1行目にはデータセットの数を示す正の整数 $t$ が含まれます。
2行目には grader が使用する乱数シードを表す2つの64ビット符号なし整数 $s_0, s_1$ ($0\le s_0,s_1\le 2^{64}-1$) が含まれます。
これらは grader.cpp の処理です。提出するソースファイルで標準入力からデータを読み取ってはいけません。
出力
各データセットに対して1行を出力します。クエリ回数が256回を超えた場合は QLE を出力します。それ以外の場合、$b$ の推測が正しければ OK を、間違っていれば WA を出力します。
これらは grader.cpp の処理です。提出するソースファイルで標準出力にデータを書き込んではいけません。
制約
テストケースの20%について、$t=1$。
別の20%のテストケースについて、$t=4$。
残りの60%のテストケースについて、$t=100$。
OJ上の grader.cpp が $25600$ 回のクエリを処理する合計時間は10msを超えないことが保証されています。
整数によるバイナリ文字列の表現について：整数の最下位ビットが最初のバイナリ文字に対応し、最上位ビットが最後のバイナリ文字に対応すると定義します。したがって、$x=x_0\circ x_1$ において、$x_0$ は $x$ の下位32ビットであり、$x_1$ は $x$ の上位32ビットです。例えば x=0xFEDCBA9876543210 の場合、x_0=0x76543210 かつ x_1=0xFEDCBA98 となります。$x_3\circ x_4$ についても同様です。
注記
配布される grader.cpp は参考用です。OJでの評価時には、異なる grader.cpp が使用されます（インターフェースの機能は同一であることが保証されます）。提出するソースファイルは interaction.h で提供されるインターフェースのみにアクセスし、grader.cpp の内部にアクセスしようとしてはなりません。