/
Time Limit: 3 sec / Memory Limit: 1024 MiB
Submission on AtCoder
When using C++
- Include
thief.hand implement the required functions.- Do not use standard input/output or file input/output.
When using other languages
Use standard input/output, following the JOIG version. Initially read N, M, and the M pairs U_i,V_i.
To ask a question, print
?followed by a string of exactly M characters, each0or1, and a newline. Do not put spaces between the bits. The bits have the same meaning as the elements of the argument ofquery. Read the answer, 0 or 1. If you receive - 1, terminate immediately.To answer, print
! A Bon one line, using the numbers of the stars containing the key and the treasure box. Answer exactly once, and ask at most 300 questions.Flush standard output after every output.
Notes
- With 300 queries, the grader and input/output may consume up to 1200 ms in total.
- There are many test cases. Terminate early on inputs you cannot solve.
Score: 100 points
Problem Statement
You are active as a thief in JOI galaxy.
There are N stars numbered from 0 to N - 1 in JOI galaxy. There are M warp devices numbered from 0 to M - 1 in JOI galaxy. The warp device i (0 \le i \le M - 1) connects star U_{i} and star V_{i} bidirectionally. It is possible to travel from any star to any star by using warp devices.
A key is hidden in a certain star, and a treasure box is hidden in another certain star. Your mission is to specify numbers, the number of the star in which the key is hidden and in which the treasure box is hidden. To achieve your mission, you can ask questions up to 300 times as below.
-
Orient each warp device. Specifically, for each warp device i (0 \le i \le M - 1), choose one of the following:
- Allow travel only from star U_{i} to star V_{i}.
- Allow travel only from star V_{i} to star U_{i}.
-
Under these conditions, ask whether it is possible to travel from the star in which the key is hidden to the star in which the treasure box is hidden by using warp devices.
You want to specify numbers, the number of the star A in which the key is hidden and the star B in which the treasure box is hidden. To achieve a higher evaluation, you want to reduce the number of questions asked.
Given information about the galaxy, write a program that determines the star A in which the key is hidden and the star B in which the treasure box is hidden, by asking questions.
Implementation Details
You need to submit one file.
The file is thief.cpp. It should implement the following function. The program should include thief.h using the preprocessing directive #include.
-
void solve(int N, int M, std::vector<int> U, std::vector<int> V)This function is called only once for each test case.
- The parameter
Nis the number of stars N. - The parameter
Mis the number of warp devices M. - The parameters
UandVare arrays of length M. For each i (0 \le i \le M - 1),U[i]andV[i]represent the stars U_i and V_i connected bi-directionally by warp device i.
- The parameter
Within thief.cpp, your program can call the following function:
-
int query(std::vector<int> x)Using this function, you can ask a question.
- The parameter
xis an array of length M. For 0 \le i \le M - 1:- If \texttt{x}[i] = 0, it means to allow travel only from star U_i to star V_i.
- If \texttt{x}[i] = 1, it means to allow travel only from star V_i to star U_i.
- The return value is 0 or 1:
- 0 means that it is not possible to travel from the star A to the star B by using warp devices.
- 1 means that it is possible to travel from the star A to the star B by using warp devices.
- The length of the parameter
xshould be M. If not, your program is judged as Wrong Answer [1]. - Each element of the parameter
xshould be 0 or 1. If not, your program is judged as Wrong Answer [2]. - You must not call function
querymore than 300 times. If it is called more than 300 times, your program is judged as Wrong Answer [3].
- The parameter
-
void answer(int A, int B)You call this function to answer the number of the star A in which the key is hidden and the star B in which the treasure box is hidden.
- The parameter
Arepresents that the key is hidden in the star A. - The parameter
Amust be between 0 and N - 1, inclusive. If not, your program is judged as Wrong Answer [4]. - The parameter
Brepresents that the treasure box is hidden in the star B. - The parameter
Bmust be between 0 and N - 1, inclusive. If not, your program is judged as Wrong Answer [5]. - If you answer a wrong number, your program is judged as Wrong Answer [6].
- The function
answershould be called exactly once. If the functionansweris called more than once, your program is judged as Wrong Answer [7]. When the functionsolveterminates, if the functionansweris not called, your program is judged as Wrong Answer [8].
- The parameter
Important Notices
- Your program can implement other functions for internal use, or use global variables.
- Your program must not use the standard input and the standard output. Your program must not communicate with other files by any methods. However, your program may output debugging information to the standard error.
Compilation and Test Run
You can download an archive file from the contest webpage which contains the sample grader to test your program. The archive file also contains a sample source file of your program.
The sample grader is the file grader.cpp. In order to test your program, put grader.cpp, thief.cpp, thief.h in the same directory, and run the following command to compile your programs.
g++ -std=gnu++20 -O2 -o grader grader.cpp thief.cpp
Instead, you may run compile.sh contained in the archive file. In this case, run the following command to compile your programs.
./compile.sh
When the compilation succeeds, the executable file grader is generated. Note that the actual grader is different from the sample grader. The sample grader will be executed as a single process, which will read input data from the standard input and write the results to the standard output.
Input for the Sample Grader
The sample grader reads the following data from the standard input.
N M A B
U_0 V_0
U_1 V_1
\vdots
U_{M - 1} V_{M - 1}
Output of the Sample Grader
The sample grader outputs the following information to the standard output (quotes for clarity).
- If your program is judged as correct, it reports the number of function calls to
queryas “Accepted: 25”. - If your program is judged as any type of Wrong Answer, the sample grader writes its type as “
Wrong Answer [4]”.
If your program satisfies the conditions of several types of Wrong Answer, the sample grader reports only one of them. The sample grader may terminate the execution when one of the conditions for wrong answer is met.
Notices for Grading
For some of the test cases, the actual grader is adaptive. This means the grader does not have a fixed answer in the beginning, and responds according to previous function calls to query. It is guaranteed that there is at least one answer which does not contradict all the responses of the the grader.
Constraints
All the input data satisfy the following conditions.
- 2 \le N \le 10\,000.
- 1 \le M \le 15\,000.
- 0 \le A \le N - 1.
- 0 \le B \le N - 1.
- A \ne B.
- 0 \le U_{i} < V_{i} \le N - 1 (0 \le i \le M - 1).
- (U_{i}, V_{i}) \ne (U_{j}, V_{j}) (0 \le i < j \le M - 1).
- It is possible to travel from any star to any star by using warp devices.
Subtasks
- (7 points) M = N - 1, U_{i} = i, V_{i} = i + 1 (0 \le i \le M - 1).
- (13 points) M = N - 1, U_{i} = 0, V_{i} = i + 1 (0 \le i \le M - 1).
- (2 points) M = N - 1, N \le 8.
- (8 points) M = N - 1, N \le 50.
- (5 points) M = N - 1, N \le 150.
- (5 points) M = N - 1, N \le 250.
- (40 points) M = N - 1.In this subtask, points are awarded as follows:
- If any test case in Subtask 7 is judged as wrong answer or exceeds the time limit, memory limit, or encounters a runtime error, the subtask score is 0 points.
- If not, let T denote maximum value of the number of function calls to
queryin all test cases of this subtask. The subtask score is determined as follows:- 20 points if 120 < T.
- 30 points if 70 < T \le 120.
- 40 points if T \le 70.
- (20 points) No additional constraints. In this subtask, points are awarded as follows:
- If any test case in Subtask 8 is judged as wrong answer or exceeds the time limit, memory limit, or encounters a runtime error, the subtask score is 0 points.
- If not, let T denote maximum value of the number of function calls to
queryin all test cases of this subtask. The subtask score is determined as follows:- 10 points if 120 < T.
- 15 points if 70 < T \le 120.
- 20 points if T \le 70.
The scores for Subtasks 1, 2, 3, 4, 5, 6 do not depend on the number of function calls to query, as long as it does not exceed 300. However, when it is more than 70, the contest system might display “Output is partially correct”.
Sample Communication
Here is a sample input for the sample grader and corresponding function calls.
Sample Input 1
5 4 0 4 0 1 0 3 1 2 1 4
Sample Function Calls
| Function Calls | Function Calls | Return Values |
|---|---|---|
solve(5, 4, [0, 0, 1, 1], [1, 3, 2, 4]) |
||
query([0, 1, 0, 0]) |
1 |
|
query([1, 1, 1, 0]) |
0 |
|
query([0, 0, 1, 0]) |
1 |
|
query([0, 0, 1, 1]) |
0 |
|
answer(0, 4) |
Choices corresponding to the 1-st function call to query are as below:
- Warp device 0 allows travel only from star 0 to star 1.
- Warp device 1 allows travel only from star 3 to star 0.
- Warp device 2 allows travel only from star 1 to star 2.
- Warp device 3 allows travel only from star 1 to star 4.
Under these conditions, it is possible to travel from star 0 to star 4 by using warp devices 0 and 3 in this order, so the return value is 1.
Choices corresponding to the 2-nd function call to query are as below:
- Warp device 0 allows travel only from star 1 to star 0.
- Warp device 1 allows travel only from star 3 to star 0.
- Warp device 2 allows travel only from star 2 to star 1.
- Warp device 3 allows travel only from star 1 to star 4.
Under these conditions, it is not possible to travel from star 0 to star 4 by using warp devices, so the return value is 0.
Choices corresponding to the 3-rd function call to query are as below:
- Warp device 0 allows travel only from star 0 to star 1.
- Warp device 1 allows travel only from star 0 to star 3.
- Warp device 2 allows travel only from star 2 to star 1.
- Warp device 3 allows travel only from star 1 to star 4.
Under these conditions, it is possible to travel from star 0 to star 4 by using warp devices, so the return value is 1.
Under the conditions of the choices corresponding to the 4-th function call to query, it is not possible to travel from 0 to star 4 by using warp devices, so the return value is 0.
The function call to answer represents that you answer that star A is star 0, and star B is star 4.
This Sample Input satisfies the constraints of Subtasks 3, 4, 5, 6, 7, 8. Among the files which can be obtained from the contest webpage, sample-01-in.txt corresponds to Sample Input 1.
Also, the function calls in a sample source file of your program contained in the archive file from the contest webpage is the same as these function calls.
AtCoder での提出方法
C++ を使用する場合
thief.hを include し,問題文で指定された関数を実装してください.- 標準入出力やファイルへの入出力を使用しないでください.
その他の言語を使用する場合
- JOIG 版の問題文の「入出力」に従ってやりとりを行ってください.
注意
- 300 回のクエリを行うと,ジャッジ側・入出力の合計で最大 1200 ms を消費します.
- テストケース数が多いため,正解できない入力では早期終了することを推奨します.
配点 : 100 点
問題文
あなたは 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 を特定するあなたの戦略を実装したプログラムを作成せよ.
実装の詳細
あなたは 1 つのファイルを提出しなければならない.
あなたの提出するファイルは thief.cpp という名前である.thief.cpp は #include プリプロセッサ指令によって thief.h を読み込み,以下の関数を実装していなければならない.
void solve(int N, int M, std::vector<int> U, std::vector<int> V)- この関数は各テストケースにおいて 1 回だけ呼び出される.
- 引数
Nは星の個数 N である. - 引数
Mはワープ装置の個数 M である. - 引数
U,Vは長さ M の配列であり,0 \leqq i \leqq M - 1 について,U[i],V[i]はワープ装置 i が双方向に結ぶ星の番号 U_i, V_i である.
thief.cpp 内では以下の関数を呼び出すことができる.
int query(std::vector<int> x)- この関数を用いて,質問を行う.
- 引数
xは長さ M の配列である.0 \leqq i \leqq M - 1 について,x[i]が 0 のときワープ装置 i について,星 U_i から星 V_i へ一方向に結ぶようにすることを,1 のときワープ装置 i について,星 V_i から星 U_i へ一方向に結ぶようにすることを表す. - 戻り値は 0 または 1 である.戻り値が 0 のときいくつかのワープ装置を用いて星 A から星 B へ移動できないことを,1 のとき星 A から星 B へ移動できることを表す.
- 引数
xの長さは M でなければならない.これが満たされていない場合,不正解 [1] と判定される. - 引数
xの各要素は,0 または 1 でなければならない.これが満たされていない場合,不正解 [2] と判定される. - 関数
queryを 300 回を超えて呼び出してはならない.300 回を超えて呼び出した場合,不正解 [3] と判定される.
void answer(int A, int B)- この関数を用いて,鍵が隠された星の番号と宝箱が隠された星の番号を解答する.
- 引数
Aは,0 以上 N - 1 以下の整数である.鍵が隠された星の番号 A を表す. - 引数
Aは,0 以上 N - 1 以下でなければならない.これが満たされていない場合,不正解 [4] と判定される. - 引数
Bは,0 以上 N - 1 以下の整数である.宝箱が隠された星の番号 B を表す. - 引数
Bは,0 以上 N - 1 以下でなければならない.これが満たされていない場合,不正解 [5] と判定される. - 誤った星の番号を解答した場合,不正解 [6] と判定される.
- 関数
answerはちょうど 1 回呼び出さなければならない.関数answerを 2 回以上呼び出した場合,不正解 [7] と判定される.関数solveの実行の終了時に関数answerが 1 回も呼び出されていなかった場合,不正解 [8] と判定される.
重要な注意
- 内部での使用のために他の関数を実装したり,グローバル変数を宣言するのは自由である.
- あなたの提出したプログラムは,標準入力・標準出力,あるいは他のファイルといかなる方法でもやりとりしてはならない.ただし,標準エラー出力にデバッグ情報等を出力することは許される.
コンパイル・実行の方法
作成したプログラムをテストするための,採点プログラムのサンプルが, コンテストサイトからダウンロードできるアーカイブの中に含まれている. このアーカイブには,提出しなければならないファイルのサンプルも含まれている.
採点プログラムのサンプルは 1 つのファイルからなる.
そのファイルは grader.cpp である.
作成したプログラムをテストするには,
これらのファイル grader.cpp, thief.cpp, thief.h を同じディレクトリに置き,次のようにコマンドを実行する.
g++ -std=gnu++20 -O2 -o grader grader.cpp thief.cpp
なお,アーカイブの中に含まれている compile.sh というファイルを代わりに実行してもよい.その場合,次のようにコマンドを実行する.
./compile.sh
コンパイルが成功すれば,grader という実行ファイルが生成される.
実際の採点プログラムは,採点プログラムのサンプルとは異なることに注意すること. 採点プログラムのサンプルは単一のプロセスとして起動する. このプログラムは,標準入力から入力を読み込み,標準出力に結果を出力する.
採点プログラムのサンプルの入力
採点プログラムのサンプルは標準入力から以下の形式で入力を読み込む.
N M A B
U_0 V_0
U_1 V_1
\vdots
U_{M - 1} V_{M - 1}
採点プログラムのサンプルの出力
採点プログラムのサンプルは標準出力へ以下の情報を出力する (引用符は実際には出力されない).
- 正解の場合,関数
queryの呼び出し回数が “Accepted: 25” のように出力される. - 不正解の場合,不正解の種類が “
Wrong Answer [4]” のように出力される.
実行するプログラムが複数の不正解の条件を満たした場合, 表示される不正解の種類はそれらのうち 1 つのみである.採点プログラムのサンプルは,不正解の条件を満たした場合,途中で実行を打ち切ることがある.
採点に関する注意
いくつかのテストケースについて,実際の採点プログラムは適応的 (adaptive) である.
これは,採点プログラムは初めから固定された答えを持たず,それ以前の query 関数の呼び出しに応じて採点プログラムが応答するということである.
ただし,すべての応答に矛盾しないような答えが少なくとも 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 つの星の間も,いくつかのワープ装置を用いることで移動できる.
小課題
- (7 点) M = N - 1,U_i = i,V_i = i + 1 (0 \leqq i \leqq M - 1).
- (13 点) M = N - 1,U_i = 0,V_i = i + 1 (0 \leqq i \leqq M - 1).
- (2 点) M = N - 1,N \leqq 8.
- (8 点) M = N - 1,N \leqq 50.
- (5 点) M = N - 1,N \leqq 150.
- (5 点) M = N - 1,N \leqq 250.
- (40 点) M = N - 1.この小課題では,以下に従い得点が決定される.
- 小課題 7 に対応するテストケースについて,1 つでも不正解があった場合,この小課題の得点は 0 点となる.
- そうでない場合,この小課題のすべてのテストケースにおける,関数
queryの呼び出し回数の最大値を T とする.このとき,小課題の得点は以下のように決定される.- 120 < T のとき,20 点.
- 70 < T \leqq 120 のとき,30 点.
- T \leqq 70 のとき,40 点.
- (20 点) 追加の制約はない.この小課題では,以下に従い得点が決定される.
- 小課題 8 に対応するテストケースについて,1 つでも不正解があった場合,この小課題の得点は 0 点となる.
- そうでない場合,この小課題のすべてのテストケースにおける,関数
queryの呼び出し回数の最大値を T とする.このとき,小課題の得点は以下のように決定される.- 120 < T のとき,10 点.
- 70 < T \leqq 120 のとき,15 点.
- T \leqq 70 のとき,20 点.
小課題 1,2,3,4,5,6 の得点は関数 query の呼び出し回数によらない (300 回以下であればよい) が,70 回より多い場合はコンテストサイトにおいて「出力は部分的に正しい」と表記されることがある.
やりとりの例
採点プログラムのサンプルが読み込む入力の例と,それに対応する関数の呼び出しの例を以下に示す.
入力例 1
5 4 0 4 0 1 0 3 1 2 1 4
関数の呼び出しの例
| 呼び出し | 呼び出し | 戻り値 |
|---|---|---|
solve(5, 4, [0, 0, 1, 1], [1, 3, 2, 4]) |
||
query([0, 1, 0, 0]) |
1 |
|
query([1, 1, 1, 0]) |
0 |
|
query([0, 0, 1, 0]) |
1 |
|
query([0, 0, 1, 1]) |
0 |
|
answer(0, 4) |
1 回目の query 関数の呼び出しに対応する選択は以下のようになる.
- ワープ装置 0 について,星 0 から星 1 へ一方向に結ぶようにする.
- ワープ装置 1 について,星 3 から星 0 へ一方向に結ぶようにする.
- ワープ装置 2 について,星 1 から星 2 へ一方向に結ぶようにする.
- ワープ装置 3 について,星 1 から星 4 へ一方向に結ぶようにする.
この選択のもとで,星 0 から星 4 へはワープ装置 0, 3 をこの順に用いることで移動できるため,戻り値は 1 となる.
2 回目の query 関数の呼び出しに対応する選択は以下のようになる.
- ワープ装置 0 について,星 1 から星 0 へ一方向に結ぶようにする.
- ワープ装置 1 について,星 3 から星 0 へ一方向に結ぶようにする.
- ワープ装置 2 について,星 2 から星 1 へ一方向に結ぶようにする.
- ワープ装置 3 について,星 1 から星 4 へ一方向に結ぶようにする.
この選択のもとで,星 0 から星 4 へはいくつかのワープ装置を用いて移動できないため,戻り値は 0 となる.
3 回目の query 関数の呼び出しに対応する選択は以下のようになる.
- ワープ装置 0 について,星 0 から星 1 へ一方向に結ぶようにする.
- ワープ装置 1 について,星 0 から星 3 へ一方向に結ぶようにする.
- ワープ装置 2 について,星 2 から星 1 へ一方向に結ぶようにする.
- ワープ装置 3 について,星 1 から星 4 へ一方向に結ぶようにする.
この選択のもとで,星 0 から星 4 へはいくつかのワープ装置を用いて移動できるため,戻り値は 1 となる.
4 回目の query 関数の呼び出しに対応する選択のもとで,星 0 から星 4 へはいくつかのワープ装置を用いて移動できないため,戻り値は 0 となる.
answer 関数の呼び出しでは星 A が星 0 であり,星 B が星 4 であると解答したことを表している.
この入力例は小課題 3,4,5,6,7,8 の制約を満たす.コンテストサイトからダウンロードできるアーカイブの中に含まれているファイルのうち,sample-01-in.txt は入力例 1 に対応する.
なお,コンテストサイトからダウンロードできるアーカイブの中に含まれている,提出しなければならないファイルのサンプルにおける関数の呼び出しは,これらの関数の呼び出しと同じである.