これは通信タスクです。このタスクでは C++ のみが使用可能であることに注意してください。

タキナとチサトはフルーツコンベンションに来ています。お気に入りのフルーツのコスプレイヤーと写真を撮って一日を過ごした後、彼女たちはゲームブースを見つけました。

ゲームのルールは以下の通りです。

• $n$ 個のフルーツがあり、それぞれ $1$ から $n$ までの異なるラベルが付いています。
• フルーツのうちちょうど $1$ つがレモンですが、タキナもチサトもまだどれがレモンかを知りません。
• タキナには $n$ 個のフルーツが順番に与えられます。彼女の目標は、レモンのラベルを（このプロセス中目隠しをしている）チサトに伝えることです。

フルーツを受け取る前に、タキナにはフルーツのラベルが現れる順序を表す配列 $p$ が与えられます。$p[1]$ は最初のフルーツのラベル、$p[2]$ は $2$ 番目のフルーツのラベル、というようになります。その後、タキナは $0$ と $1$ のみからなるバイナリ文字列 $b$ を書き出します。文字列の長さは $5000$ 文字以下でなければなりませんが、空であっても構いません。$b$ の長さを $x$ とします。

その後、フルーツが前述の順序でタキナに $1$ つずつ与えられます。各フルーツを受け取るたびに、タキナはそのフルーツがレモンかどうかを知らされます。

• そのフルーツがレモンではない場合、タキナはそれを食べるかどうかを選択できます。この決定は次のフルーツを受け取る前に行う必要があり、変更することはできません。
• そのフルーツがレモンである場合、タキナはそれを食べてはいけません。

タキナが食べたフルーツの総数を $y$ とします。

最後に、チサトは文字列 $b$ と、食べられなかったフルーツのラベルのソート済みリストを受け取ります。この情報を使用して、チサトはレモンであるフルーツのラベルを特定しなければなりません。

タキナとチサトはこのゲームを $t$ 回プレイすることにしました。$x$ と $y$ の両方を最小化しつつ、レモンを正しく特定するための戦略を設計してください。

実装の詳細

これは通信タスクです。標準入力からの読み込みや標準出力への書き出しは行わないでください。

以下の $3$ つのプロシージャを実装する必要があります。

タキナのために、以下を実装してください。

std::string init(int subtask, int n, std::vector<int> p)

• subtask: テストケースが属するサブタスクのインデックス。
• n: フルーツの数。
• p: 長さ $n + 1$ の配列。ここで：
  • $p[0] = 0$
  • 各 $1 \le i \le n$ に対して、$p[i]$ はタキナに与えられる $i$ 番目のフルーツのラベル。
• このプロシージャはテストケースごとに $t$ 回、各ゲームの開始時に $1$ 回ずつ呼び出されます。

このプロシージャは、長さが $0$ 以上 $5000$ 以下の、$0$ と $1$ のみからなる文字列 $b$ を返す必要があります。無効な長さや形式の文字列が返された場合、Wrong Answer 判定となります。

bool receive_fruit(int id, bool is_lemon)

• id: タキナに与えられたフルーツのラベル。
• is_lemon: 与えられたフルーツがレモンであれば true、そうでなければ false。
• このプロシージャは $t$ 回のゲームのそれぞれについて $n$ 回、各フルーツに対して $1$ 回ずつ呼び出されます。

このプロシージャは、フルーツを食べるべきであれば true を、そうでなければ false を返す必要があります。is_lemon が true のときに true を返すと、Wrong Answer 判定となります。

チサトのために、以下を実装してください。

int answer(int subtask, int n, std::string b, std::vector<int> uneaten)

• subtask: テストケースが属するサブタスクのインデックス。
• n: フルーツの数。
• b: init が返した文字列。
• uneaten: タキナが食べなかったフルーツのラベルの長さ $n - y + 1$ のソート済みベクトル。ここで：
  • uneaten[0] = 0
  • uneaten[i] は食べられなかったフルーツの中で $i$ 番目に小さいラベル。
• このプロシージャはテストケースごとに $t$ 回、各ゲームの終了時に $1$ 回ずつ呼び出されます。

このプロシージャは、レモンのラベルである整数を返す必要があります。戻り値が正しいラベルと一致しない場合、Wrong Answer 判定となります。

実際の採点では、上記のプロシージャを呼び出すプログラムが 2回 実行されます。

1. 1回目の実行では、以下のステップが $t$ 回実行されます。
   • init が $1$ 回呼び出されます。
   • receive_fruit がタキナに与えられるフルーツの順序に従って $n$ 回呼び出されます。
   • プログラムは連続する呼び出し間で情報を保存および保持できます。
2. 2回目の実行では、ゲームの順序が1回目と異なる場合があります。$t$ 回の各ゲームに対して：
   • answer が $1$ 回呼び出されます。answer に渡されるパラメータ以外、プログラムは1回目の実行からの情報にアクセスできません。

プロシージャは複数回呼び出される可能性があるため、前回の呼び出しからの残りのデータが現在の呼び出しに与える影響に注意を払う必要があります。

制約

すべてのテストケースにおいて、入力は以下の範囲を満たします。

• $1 \le t \le 10\,000$
• $n = 500$
• すべての $1 \le i \le n$ に対して $1 \le p[i] \le n$
• レモンはちょうど $1$ つ存在する。

各サブタスクにおいて、プログラムはタキナが書き出す文字列の長さ $x$ と、彼女が食べるフルーツの数 $y$ に基づいて異なるスコアが与えられます。各テストケースのスコアは、すべての $t$ 回のゲームにおける $x$ の最大値と $y$ の最大値を使用して計算されます。

入出力例

入力 1

(デモンストレーション用の入力データ)

出力 1

(デモンストレーション用の出力データ)

注記

単一のゲーム ($t = 1$) で $n = 4$ の場合を考えます。これは入力制約を満たしておらず、デモンストレーション目的でのみ使用されることに注意してください。タキナに与えられるフルーツの順序が $p = [0, 3, 1, 4, 2]$ であると仮定します。これは、フルーツがラベルの順序 $3, 1, 4, 2$ で提示されることを意味します。ラベル $4$ のフルーツがレモンであると仮定します。

この例では、タキナはラベル $3$ と $2$ のフルーツを食べるため、食べられなかったフルーツは $\{1, 4\}$ です。したがって、answer に渡されるベクトル uneaten は [0, 1, 4] となります。b と uneaten を使用して、プロシージャ answer はレモンのラベルである $4$ を返します。この戦略により、$x = 3$ かつ $y = 2$ でレモンを正しく特定できました。

テスト

サンプルグレーダー (grader.cpp)、ヘッダーファイル (lemon.h)、およびソリューションテンプレート (lemon.cpp) は添付ファイルからダウンロードできます。テスト用に sample1.txt と sample2.txt の2つの入力ファイルが提供されています。compile.sh を使用してコンパイルし、run.sh を使用してソリューションを実行し、テストを行うことができます。

この問題では CMS ユーザーテストはサポートされていません。

サンプルグレーダー

サンプルグレーダーは、実装をローカルでテストするのに役立ちます。公式グレーダーとは異なり、サンプルグレーダーはプログラムを一度だけ実行し、タキナとチサトのテスト順序を変更しません。

入力形式

入力の最初の行には整数 subtask が含まれます。 入力の2行目には整数 t が含まれます。 続く $t$ 行の入力はそれぞれ1つのゲームを表します。各ゲームは以下のように記述されます。

• フルーツの数 $n$ とレモンのラベル $l$ を表す、スペース区切りの2つの整数。
• $n$ 個のスペース区切りの整数 $p[1], p[2], \dots, p[n]$。

出力形式

サンプルグレーダーは、すべてのゲームにおける $x$ と $y$ の値から計算されたスコアの割合を表す単一の実数を出力します。

注記

追加の診断メッセージが標準エラーに出力される場合があります。サンプルグレーダーは公式グレーダーの動作をシミュレートしません。