D - 宇宙怪盗 (Space Thief) Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点： 100 点

配布ファイル

注意

  • 300 回のクエリを行うと，ジャッジ側・入出力の合計で最大 1200 ms を消費します．
  • テストケース数が多いため，正解できない入力では早期終了することを推奨します．

あなたは JOI 銀河で怪盗として活躍している．

JOI 銀河には 0 から N - 1 までの番号が付けられている N 個の星がある．また，0 から M - 1 までの番号が付けられている M 個のワープ装置がある．ワープ装置 i (0 \leqq i \leqq M - 1) は星 U_i と星 V_i の間を双方向に結んでいる．どの 2 つの星の間も，いくつかのワープ装置を用いることで移動できる．

JOI 銀河のある星には鍵が隠されており，別の星には宝箱が隠されている．あなたのミッションは，鍵と宝箱が隠されている星の番号を特定することである．そのために，以下の質問を 300 回まで行うことができる．

  • それぞれのワープ装置 i (0 \leqq i \leqq M - 1) について，星 U_i から星 V_i へ一方向のみに結ぶようにするか星 V_i から星 U_i へ一方向のみに結ぶようにするかを選択する．
  • そのもとで，いくつかのワープ装置を用いて鍵のある星から宝箱のある星へ移動できるかを尋ねる．

あなたは質問を行うことで，鍵が隠された星の番号である A と宝箱が隠された星の番号である B を特定したい．ミッションで高い評価を得るために，質問の回数はできるだけ少なくしたい．

銀河の情報が与えられたとき，質問を行うことで，鍵が隠された星の番号 A と宝箱が隠された星の番号 B を特定するあなたの戦略を実装したプログラムを作成せよ．

入出力

この問題は インタラクティブ問題（あなたが作成したプログラムとジャッジプログラムが標準入出力を介して対話を行う形式の問題）である．

最初に，銀河の情報が以下の形式で標準入力から与えられる．

N M
U_0 V_0
U_1 V_1
\vdots
U_{M-1} V_{M-1}

あなたのプログラムはこれを受け取った後，採点プログラムとやり取りを行わなければならない．

質問を行うには，以下の形式で採点プログラムとやり取りせよ．

  • まず，以下の形式で標準出力に出力せよ．
    ? x_0 x_1 x_2 \cdots x_{M - 1}
    • 0 \leqq i \leqq M - 1 について，x_i は文字 0 または 1 であり，これらの間には空白を入れず長さ M の文字列として出力せよ（? の直後にのみ空白を入れること）． この文字列の長さが M でない場合，不正解 [1] と判定される．
    • 0 \leqq i \leqq M - 1 について，x_i が 0 でも 1 でもない場合，不正解 [2] と判定される．
    • 0 \leqq i \leqq M - 1 について，x_i が 0 のときワープ装置 i について，星 U_i から星 V_i へ一方向に結ぶようにすることを，1 のときワープ装置 i について，星 V_i から星 U_i へ一方向に結ぶようにすることを表す．
  • その後，質問の回答を表す整数 r が以下の形式で標準入力から与えられる．
    r

    ここで，r は 0, 1, -1 のいずれかであり，それぞれ以下を表す．
    • r が 0 のとき，星 A から星 B へ移動できないことを表す．
    • r が 1 のとき，星 A から星 B へ移動できることを表す．
    • r が -1 のとき，採点プログラムがあなたのプログラムを不正解であると判定したことを表す．この場合，ただちにあなたのプログラムを終了せよ．

質問を 300 回を超えて行ってはならない．300 回を超えて行った場合，不正解 [3] と判定される．

鍵が隠された星の番号と宝箱が隠された星の番号を解答するには，以下の形式で標準出力に出力せよ．

! A B
  • A は 0 以上 N - 1 以下の整数である．鍵が隠された星の番号 A を表す．
  • A は，0 以上 N - 1 以下でなければならない．これが満たされていない場合，不正解 [4] と判定される．
  • B は 0 以上 N - 1 以下の整数である．宝箱が隠された星の番号 B を表す．
  • B は，0 以上 N - 1 以下でなければならない．これが満たされていない場合，不正解 [5] と判定される．
  • 誤った星の番号を解答した場合，不正解 [6] と判定される．
  • 解答はちょうど 1 回行わなければならない．2 回以上解答した場合，不正解 [7] と判定される．あなたのプログラムの実行の終了時に解答が 1 回も行われていなかった場合，不正解 [8] と判定される．

上にあげたいずれでもない形式で標準出力に出力した場合，不正解 [9] と判定される．

重要な注意

  • 各出力の最後には，必ず標準出力を flush せよ．flush しない場合，実行時間制限超過と判定される可能性がある．
  • C++ のプログラムを提出する場合，cout << endl; によって，改行されるとともに自動的に flush される．もし printf を使用する場合，fflush(stdout) を用いよ．
  • Python のプログラムを提出する場合，入力に input() を使う限り自動的に flush される．
  • 質問の際に -1 を受け取った場合，ただちにプログラムを終了せよ．終了しなかった場合，実行結果は不定である．

採点に関する注意

いくつかのテストケースについて，実際の採点プログラムは適応的 (adaptive) である．これは，採点プログラムは初めから固定された答えを持たず，それ以前の質問に応じて採点プログラムが応答するということである．ただし，すべての応答に矛盾しないような答えが少なくとも 1 つ存在するということが保証される．

テストツール

作成したプログラムをテストするためのテストツール testing_tool.py が，コンテストサイトからダウンロードできるアーカイブの中に含まれている．このツールを必ずしも使う必要はなく，また変更することも許される．実際の採点プログラムはテストツールとは異なることに注意すること．特に，テストツールは適応的 (adaptive) でなく，初めから固定された答えを持つ．

あなたのプログラムが C++ で実装されている場合，作成したプログラムをテストするには，以下のような手順に従えばよい．

  • あなたのプログラムをコンパイルして実行ファイルを生成せよ．例えば，あなたのプログラムが thief.cpp という名前の場合，以下のようなコマンドを実行すれば thief という実行ファイルが生成される．

    g++ -std=gnu++20 -O2 -o thief thief.cpp

  • 次に，以下のコマンドを実行せよ．

    python3 testing_tool.py ./thief

あなたのプログラムが Python で実装されている場合，例えば，あなたのプログラムが thief.py という名前なら，以下のコマンドを実行せよ．

python3 testing_tool.py pypy3 thief.py

テストツールの入力

テストツールは標準入力から以下の形式で入力を読み込む．

N M A B
U_0 V_0
U_1 V_1
\vdots
U_{M-1} V_{M-1}

テストツールの出力

プログラムの実行が正常に終了した場合，テストツールは標準出力へ以下の情報を出力する（引用符は実際には出力されない）．

  • 正解の場合，質問の回数が Accepted: 25 のように出力される．
  • 不正解の場合，不正解の種類が Wrong Answer [4] のように出力される．

実行するプログラムが複数の不正解の条件を満たした場合，表示される不正解の種類はそれらのうち 1 つのみである．

制約

すべての入力データは以下の条件を満たす．

  • 2 \leqq N \leqq 10\,000．
  • 1 \leqq M \leqq 15\,000．
  • 0 \leqq A \leqq N - 1．
  • 0 \leqq B \leqq N - 1．
  • A \neq B．
  • 0 \leqq U_i < V_i \leqq N - 1 (0 \leqq i \leqq M - 1)．
  • (U_i, V_i) \neq (U_j, V_j) (0 \leqq i < j \leqq M - 1)．
  • どの 2 つの星の間も，いくつかのワープ装置を用いることで移動できる．
  • 入力される値はすべて整数である．

小課題

  1. (11 点) M = N - 1，U_i = i，V_i = i + 1 (0 \leqq i \leqq M - 1)．
  2. (21 点) M = N - 1，U_i = 0，V_i = i + 1 (0 \leqq i \leqq M - 1)．
  3. (4 点) M = N - 1，N \leqq 8．
  4. (12 点) M = N - 1，N \leqq 50．
  5. (8 点) M = N - 1，N \leqq 150．
  6. (8 点) M = N - 1，N \leqq 250．
  7. (32 点) M = N - 1．この小課題では，以下に従い得点が決定される．
    • 小課題 7 に対応するテストケースについて，1 つでも不正解があった場合，この小課題の得点は 0 点となる．
    • そうでない場合，この小課題のすべてのテストケースにおける，関数 query の呼び出し回数の最大値を T とする．このとき，小課題の得点は以下のように決定される．
      • 120 < T のとき，16 点．
      • 70 < T \leqq 120 のとき，24 点．
      • T \leqq 70 のとき，32 点．
  8. (4 点) 追加の制約はない．この小課題では，以下に従い得点が決定される．
    • 小課題 8 に対応するテストケースについて，1 つでも不正解があった場合，この小課題の得点は 0 点となる．
    • そうでない場合，この小課題のすべてのテストケースにおける，関数 query の呼び出し回数の最大値を T とする．このとき，小課題の得点は以下のように決定される．
      • 120 < T のとき，2 点．
      • 70 < T \leqq 120 のとき，3 点．
      • T \leqq 70 のとき，4 点．

小課題 1,2,3,4,5,6 の得点は質問の回数によらない (300 回以下であればよい) が，70 回より多い場合はコンテストサイトにおいて「出力は部分的に正しい」と表記されることがある．

やりとりの例

テストツールが読み込む入力の例と，それに対応するやり取りの例を以下に示す．

入力例 1

5 4 0 4
0 1
0 3
1 2
1 4
7be724b9ba153c7baf9de60727f76fc6.png

1 回目の質問に対応する選択は以下のようになる．

  • ワープ装置 0 について，星 0 から星 1 へ一方向に結ぶようにする．
  • ワープ装置 1 について，星 3 から星 0 へ一方向に結ぶようにする．
  • ワープ装置 2 について，星 1 から星 2 へ一方向に結ぶようにする．
  • ワープ装置 3 について，星 1 から星 4 へ一方向に結ぶようにする．

この選択のもとで，星 0 から星 4 へはワープ装置 0, 3 をこの順に用いることで移動できるため，戻り値は 1 となる．

2 回目の質問に対応する選択は以下のようになる．

  • ワープ装置 0 について，星 1 から星 0 へ一方向に結ぶようにする．
  • ワープ装置 1 について，星 3 から星 0 へ一方向に結ぶようにする．
  • ワープ装置 2 について，星 2 から星 1 へ一方向に結ぶようにする．
  • ワープ装置 3 について，星 1 から星 4 へ一方向に結ぶようにする．

この選択のもとで，星 0 から星 4 へはいくつかのワープ装置を用いて移動できないため，戻り値は 0 となる．

3 回目の質問に対応する選択は以下のようになる．

  • ワープ装置 0 について，星 0 から星 1 へ一方向に結ぶようにする．
  • ワープ装置 1 について，星 0 から星 3 へ一方向に結ぶようにする．
  • ワープ装置 2 について，星 2 から星 1 へ一方向に結ぶようにする．
  • ワープ装置 3 について，星 1 から星 4 へ一方向に結ぶようにする．

この選択のもとで，星 0 から星 4 へはいくつかのワープ装置を用いて移動できるため，戻り値は 1 となる．

4 回目の質問に対応する選択のもとで，星 0 から星 4 へはいくつかのワープ装置を用いて移動できないため，戻り値は 0 となる．

最後に，星 A が星 0 であり，星 B が星 4 であると解答している．

この入力例は小課題 3,4,5,6,7,8 の制約を満たす．コンテストサイトからダウンロードできるアーカイブの中に含まれているファイルのうち，sample-01-in.txt は入力例 1 に対応する．