/
実行時間制限: 10 sec / メモリ制限: 1024 MiB
Submission on AtCoder
Using C++
Include
dango3.hand implement all functions in a single source file.Using standard input and output
First, N, M are given in this order on one line.
Query
Consider an array A of length N \times M, with A[i] = 1 if dango i is selected and A[i] = 0 otherwise. Print the character
Q, immediately followed by A as packed binary bytes, then a newline. Pack eight elements in each byte, starting with the least significant bit. Do not print a string of ASCII0and1characters.For example, if A = (0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0), print
Q 4followed by a newline. The two bytes afterQhave values 32 and 52, which appear as a space and the character4. Do not add a separator betweenQand the binary data.The return value of
Queryis then given on one line.Answer
Define the selection array A in the same way. Print the character
A, immediately followed by A in the same binary format, then a newline. The integer0is then given on one line.Other instructions
- If the output format is incorrect or a Wrong Answer condition is met, the input you receive is
-1. Terminate your program immediately in this case.- After M calls to
Answer, print the characterF.- Flush after every output.
Score: 100 points
Problem Statement
JOI-kun is a professional confectioner making dangos (Japanese dumplings). In JOI-kun’s shop, the colors of dangos are specified. There are N colors of dangos, numbered from 1 to N.
A beautiful dango stick is a famous item in JOI-kun’s shop. A beautiful dango stick is made of N dangos of different colors skewered with a stick.
For each of the N colors, JOI-kun has M dangos of that color. Therefore, JOI-kun has N \times M dangos in total. These dangos are numbered from 1 to N \times M. Using these dangos and M sticks, JOI-kun wants to make M beautiful skewered dango sticks.
To avoid a mistake about the colors of the dangos, JOI-kun will use a dango checker. If JOI-kun inputs the indices of some dangos, the dango checker answers the maximum number of beautiful dango sticks he can make using the dangos in the input and sufficiently many sticks.
Using the dango checker several times, JOI-kun wants to divide the N \times M dangos into M groups. Every group should consist of N dangos, and contain a dango of each color.
JOI-kun wants to divide the N \times M dangos into M groups using the dango checker at most 50 000 times.
Write a program which, given information of the dangos, implements JOI-kun’s strategy to divide the dangos into groups using the the dango checker at most 50 000 times.
Implementation Details
You need to submit one file. The name of the file is dango3.cpp. It should implement the following function. The program should include dango3.h using the preprocessing directive #include.
void Solve(int N, int M)This function is called once for each test case.- The parameter
Nis the number of colors of dangos N. - The parameter
Mis the number of beautiful dango sticks M JOI-kun wants to make.
- The parameter
Your program may call the following functions.
int Query(const std::vector<int> &x)Using this function, your program asks questions to the dango checker.- The parameter
xis the list of the indices of the dangos sent to the dango checker. - The return value is the maximum number of beautiful dango sticks JOI-kun can make using the dangos specified by the parameter
xand sufficiently many sticks. - Each element of the parameter
xshould be between 1 and N \times M, inclusive. If this condition is not satisfied, your program is judged as Wrong Answer [1]. - The elements of the parameter
xshould be different from each other. If this condition is not satisfied, your program is judged as Wrong Answer [2]. - It is not allowed to call the function
Querymore than 50 000 times. If the functionQueryis called more than 50 000 times, your program is judged as Wrong Answer [3].
- The parameter
void Answer(const std::vector<int> &a)Using this function, your program answers groups of dangos to make beautiful dango sticks.- The parameter
ais the list of the indices of dangos for a beautiful dango stick. - The length of the parameter
ashould be N. If this condition is not satisfied, your program is judged as Wrong Answer [4]. - Every element of the parameter
ashould be between 1 and N \times M, inclusive. If this condition is not satisfied, your program is judged as Wrong Answer [5]. - Throughout the process, no value should appear in a more than once. If this condition is not satisfied, your program is judged as Wrong Answer [6].
- If it is impossible to make a beautiful dango stick using the dangos specified by
aand a stick, your program is judged as Wrong Answer [7]. - The function
Answershould be called exactly M times. If the number of function calls toAnsweris different from M when the functionSolveterminates, 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, dango3.cpp, dango3.h in the same directory, and run the following command to compile your programs.
g++ -std=gnu++17 -O2 -o grader grader.cpp dango3.cpp
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
C_{1} C_{2} \cdots C_{N\times M}
Here C_{i} (1 \le i \le N \times M) is the color of the dango i. It is an integer between 1 and N, inclusive.
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 writes the number of times of the function calls to
Queryas “Accepted: 2022”. - If your program is judged as any one 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.
Constraints
All input data satisfy the following constraints. For the values of C, see Input for the Sample Grader.
- 1 \le C_{i} \le N (1 \le i \le N \times M).
- For each j (1 \le j \le N), there are exactly M indices i (1 \le i \le N \times M) satisfying C_{i} = j.
- N, M are integers.
- C_{i} (1 \le i \le N \times M) is an integer.
Subtasks
- (5 points) N = 4, M = 4.
- (12 points) N = 100, M = 10.
- (22 points) N = 200, M = 25.
- (61 points) N = 400, M = 25.
Sample Communication
Here is a sample input for the sample grader and corresponding function calls.
Sample Input 1
3 2 3 3 1 2 1 2
Sample Function Calls
| Call | Call | Return Value |
|---|---|---|
Solve(3, 2) |
||
Query([]) |
0 |
|
Query([4, 2, 1 ,3]) |
1 |
|
Query([3, 4, 5]) |
0 |
|
Query([2, 6, 5]) |
1 |
|
Query([6, 5, 4, 3, 2, 1]) |
2 |
|
Answer([1, 6, 5]) |
||
Answer([2, 3, 4]) |
Note that this sample input does not satisfy the constraints of any subtask.
Among the files which can be downloaded from the contest webpage, sample-02.txt satisfies the constraints of Subtask 1.
AtCoder での提出方法
C++ を使用する場合
dango3.hをインクルードし,すべての関数を 1 つのファイル内で実装して提出してください.標準入出力を使用する場合
はじめに,N, M がこの順に 1 行で与えられます.
Query
団子 i を選ぶとき A[i] = 1,選ばないとき A[i] = 0 とする長さ N \times M の配列 A を考えます.文字
Qを出力し,その後空白を空けずに A をバイナリで出力し,最後に改行してください.8 要素を 1 バイトにまとめ,下位ビットから順に詰めます.ASCII の0と1を並べた文字列ではありません.例えば A = (0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0) のとき,
Q 4を出力し,改行してください.この例ではQに続く 2 バイトの値が 32 と 52 なので,見た目は空白と文字4になります.Qとバイナリデータの間に区切りの空白は加えません.その後,
Queryの戻り値が 1 行で与えられます.Answer
同様に選択を表す配列 A を考えます.文字
Aを出力し,その後空白を空けずに A を同じバイナリ形式で出力し,最後に改行してください.その後,0が 1 行で与えられます.その他
- 出力形式が正しくない場合や不正解の条件に当てはまった場合,与えられる入力は
-1になります.この場合,ただちにプログラムを終了してください.- M 回の
Answerの後,文字Fを出力してください.- 各出力の後には必ず flush をしてください.
配点 : 100 点
問題文
JOI 君は団子職人である.JOI 君の店で用いられる団子にはそれぞれ色が定まっており,色は N 種類ある.色には 1 から N までの番号が付けられている.
JOI 君の店の人気メニューはきれいな串団子である.きれいな串団子とは,色が相異なる合計 N 個の団子に 1 本の串を刺したものである.
JOI 君は色 1 から色 N までの団子をそれぞれ M 個ずつ,合計 N \times M 個の団子を用意している.これらの団子には 1 から N \times M までの番号が付けられている.JOI 君はこれらの団子と M 本の串からきれいな串団子を M 本作りたい.
団子の色を間違えてはならないため,JOI 君は団子チェッカーを用いることにした.団子チェッカーにいくつかの団子の番号を指定して質問すると,それらの団子と十分な量の串を用いて最大何本のきれいな串団子を作れるかを知ることができる.
JOI 君は団子チェッカーに何度か質問をすることで,M 本のきれいな串団子を作るために,N \times M 個ある団子を N 個ずつ M 組に分けたい.このとき,それぞれの組には色 1 から色 N までの団子が 1 つずつ含まれていなければならない.
JOI 君は団子チェッカーに 50\,000 回以下の質問を行うことで,団子を組分けしたい.
団子の情報が与えられたとき,団子チェッカーに 50\,000 回以下の質問を行うことで団子を組分けする JOI 君の戦略を実装したプログラムを作成せよ.
実装の詳細
あなたは 1 つのファイルを提出しなければならない.
あなたの提出するファイルは dango3.cpp という名前である.このファイルは以下の関数を実装していなければならない.そのプログラムは #include プリプロセッサ指令によって dango3.h を読み込むこと.
void Solve(int N, int M)この関数は各テストケースにおいて 1 回だけ呼び出される.- 引数
Nは団子の色の種類の数 N である. - 引数
Mは JOI 君が作りたいきれいな串団子の本数 M である.
- 引数
あなたのプログラムは以下の関数を呼び出すことができる.
int Query(const std::vector<int> &x)この関数を用いて,団子チェッカーに質問を行う.- 引数
xは,団子チェッカーに質問する団子の番号のリストである. - 戻り値は,指定した団子と十分な量の串を用いて作れるきれいな串団子の本数の最大値である.
- 引数
xの各要素は,1 以上 N \times M 以下でなければならない.これが満たされていない場合,不正解 [1] と判定される. - 引数
xの各要素はすべて異ならなければならない.これが満たされていない場合,不正解 [2] と判定される. - 関数
Queryを 50\,000 回を超えて呼び出してはならない.50\,000 回を超えて呼び出した場合,不正解 [3] と判定される.
- 引数
void Answer(const std::vector<int> &a)この関数を用いて,きれいな串団子を作るための団子の組を解答する.- 引数
aは, きれいな串団子を作るための団子の番号のリストである. - 引数
aの長さは,N でなければならない.これが満たされていない場合,不正解 [4] と判定される. - 引数
aの各要素は,1 以上 N \times M 以下でなければならない.これが満たされていない場合,不正解 [5] と判定される. aの要素に同じ値を累計で 2 回以上指定してはならない.これが満たされていない場合,不正解 [6] と判定される.aで指定された各団子と 1 本の串を用いてきれいな串団子を作ることができない場合,不正解 [7] と判定される.- 関数
Answerはちょうど M 回呼び出される必要がある.関数Solveの実行の終了時に関数Answerの呼び出し回数が M 回でなかった場合,不正解 [8] と判定される.
- 引数
重要な注意
- 内部での使用のために他の関数を実装したり,グローバル変数を宣言するのは自由である.
- あなたの提出したプログラムは,標準入力・標準出力,あるいは他のファイルといかなる方法でもやりとりしてはならない.ただし,標準エラー出力にデバッグ情報等を出力することは許される.
コンパイル・実行の方法
作成したプログラムをテストするための,採点プログラムのサンプルが,コンテストサイトからダウンロードできるアーカイブの中に含まれている.このアーカイブには,提出しなければならないファイルのサンプルも含まれている.
採点プログラムのサンプルは 1 つのファイルからなる. そのファイルは grader.cpp である.作成したプログラムをテストするには,これらのファイル grader.cpp, dango3.cpp, dango3.h を同じディレクトリに置き,次のようにコマンドを実行する.
g++ -std=gnu++17 -O2 -o grader grader.cpp dango3.cpp
コンパイルが成功すれば,grader という実行ファイルが生成される.
実際の採点プログラムは,採点プログラムのサンプルとは異なることに注意すること.採点プログラムのサンプルは単一のプロセスとして起動する.このプログラムは,標準入力から入力を読み込み,標準出力に結果を出力する.
採点プログラムのサンプルの入力
採点プログラムのサンプルは標準入力から以下の形式で入力を読み込む.
N M
C_{1} C_{2} \cdots C_{N\times M}
C_{i} (1 \leqq i \leqq N \times M) は,団子 i の色を表す,1 以上 N 以下の整数である.
採点プログラムのサンプルの出力
採点プログラムのサンプルは標準出力へ以下の情報を出力する (引用符は実際には出力されない).
- 正解の場合,関数
Queryの呼び出し回数が “Accepted: 2022” のように出力される. - 不正解の場合,不正解の種類が “
Wrong Answer [4]” のように出力される.
実行するプログラムが複数の不正解の条件を満たした場合,表示される不正解の種類はそれらのうち 1 つのみである.
制約
すべての入力データは以下の条件を満たす.C の意味については「採点プログラムのサンプルの入力」の項目を参照せよ.
- 1 \leqq C_{i} \leqq N (1 \leqq i \leqq N \times M).
- 各 j (1 \leqq j \leqq N) に対し,C_{i} = j となる i (1 \leqq i \leqq N \times M) がちょうど M 個存在する.
- N, M は整数である.
- C_{i} (1 \leqq i \leqq N \times M) は整数である.
小課題
- (5 点) N = 4,M = 4.
- (12 点) N = 100,M = 10.
- (22 点) N = 200,M = 25.
- (61 点) N = 400,M = 25.
やりとりの例
採点プログラムのサンプルが読み込む入力の例と,それに対応する関数の呼び出しの例を以下に示す.
入力例 1
3 2 3 3 1 2 1 2
関数の呼び出しの例
| 呼び出し | 呼び出し | 戻り値 |
|---|---|---|
Solve(3, 2) |
||
Query([]) |
0 |
|
Query([4, 2, 1 ,3]) |
1 |
|
Query([3, 4, 5]) |
0 |
|
Query([2, 6, 5]) |
1 |
|
Query([6, 5, 4, 3, 2, 1]) |
2 |
|
Answer([1, 6, 5]) |
||
Answer([2, 3, 4]) |
この入力例はどの小課題の制約も満たさないことに注意すること.
コンテストサイトからダウンロードできるファイルのうち,sample-02.txt は小課題 1 の制約を満たす.