/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 550 点
問題文
この問題は インタラクティブな問題（あなたの作成したプログラムとジャッジシステムが入出力を介して対話を行う形式の問題）です。
整数 N および N 未満の 奇数 K が与えられます。
ジャッジシステムは、0 および 1 からなる長さ N の数列 A = (A_1, A_2, \dots, A_N) を隠し持っています。
あなたは数列 A の要素の値を直接知ることはできません。
その代わりに、ジャッジシステムに対して以下の質問を N 回まで行うことができます。
- 1 以上 N 以下の相異なる整数 x_1, x_2, \dots, x_K を選ぶ。そして、A_{x_1} + A_{x_2} + \dots + A_{x_K} の偶奇を聞く。
N 回以下の質問で (A_1, A_2, \dots, A_N) を全て特定して、答えを出力してください。
ただし、ジャッジは適応的です。言い換えると、ジャッジシステムは今までの質問の回答に矛盾しない範囲でA の内容を自由に変更することができます。
そのため、出力が次の条件を満たす場合にあなたの作成したプログラムは正解とみなされます。それ以外の場合は不正解とみなされます。
- ここまでの質問の回答と矛盾しないような数列が一意に定まっており、かつそれがプログラムが出力した数列と一致している。
制約
- 1 \leq K \lt N \leq 1000
- K は奇数
- A_i は 0 または 1
入出力
この問題はインタラクティブな問題（あなたの作成したプログラムとジャッジシステムが入出力を介して対話を行う形式の問題）です。
最初に、N および K を標準入力から受け取ってください。
N K
次に、(A_1, A_2, \dots, A_N) を全て特定できるまで質問を繰り返してください。
質問は、以下の形式で標準出力に出力してください。ここで x_1, x_2, \dots, x_K は 1 以上 N 以下の相異なる K 個の整数です。
? x_1 x_2 \dots x_K
これに対する応答は、次の形式で標準入力から与えられます。
T
ここで、T は質問に対する答えで、
- T が
0である場合は A_{x_1} + A_{x_2} + \dots + A_{x_K} は偶数であることを、 - T が
1である場合は A_{x_1} + A_{x_2} + \dots + A_{x_K} は奇数であることを意味します。
ただし、x_1, x_2, \dots, x_K が制約を満たしていないか、質問の回数が N 回を超えた場合は T は -1 となります。
ジャッジが -1 を返した場合、プログラムはすでに不正解とみなされています。この場合、ただちにプログラムを終了してください。
A の要素を全て特定できたら、特定した A の要素を以下の形式で出力してください。その後、ただちにプログラムを終了してください。
! A_1 A_2 \dots A_N
注意点
- 出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。
- 対話の途中で誤った出力形式による出力を行った、あるいはプログラムが途中で終了した場合のジャッジ結果は不定です。
- 解答を出力したらただちにプログラムを終了してください。そうしない場合、ジャッジ結果は不定です。
- ジャッジは適応的です。言い換えると、ジャッジシステムは今までの質問の回答に矛盾しない範囲で A の内容を変更することができます。
入出力例
以下の入出力例は N=5, K=3 の場合の入出力例です。この入出力例の通りに出力するとジャッジ結果は WA になることに注意してください。
入出力例では、プログラムが出力した A = (1, 0, 1, 1, 0) はここまでの質問の回答に矛盾しない数列ですが、例えば (0, 0, 1, 0, 0) もここまでの質問の回答に矛盾しない数列であるため、数列 A は一意に定まっていません。そのため、このプログラムは不正解とみなされます。
| 入力 | 出力 | 説明 |
|---|---|---|
5 3 | まず整数 N および K が与えられます。 | |
? 2 4 1 | (x_1, x_2, x_3) = (2, 4, 1) として質問を行います。 | |
0 | 質問の答えは 0 なので、ジャッジはその値を返します。 | |
? 5 3 2 | (x_1, x_2, x_3) = (5, 3, 2) として質問を行います。 | |
1 | 質問の答えは 1 なので、ジャッジはその値を返します。 | |
! 1 0 1 1 0 | A の答えとして (1, 0, 1, 1, 0) を出力します。A を一意に特定できていないのでジャッジ結果は WA になります。 |
Score : 550 points
Problem Statement
This is an interactive task (where your program and the judge interact via Standard Input and Output).
You are given an integer N and an odd number K.
The judge has a hidden length-N sequence A = (A_1, A_2, \dots, A_N) consisting of 0 and 1.
While you cannot directly access the elements of sequence A, you are allowed to ask the judge the following query at most N times.
- Choose distinct integers x_1, x_2, \dots, and x_K between 1 and N, inclusive, to ask the parity of A_{x_1} + A_{x_2} + \dots + A_{x_K}.
Determine (A_1, A_2, \dots, A_N) by at most N queries, and print the answer.
Here, the judge is adaptive. In other words, the judge may modify the contents of A as long as it is consistent with the responses to the past queries.
Therefore, your program is considered correct if the output satisfies the following condition, and incorrect otherwise:
- your program prints a sequence consistent with the responses to the queries so far, and that is the only such sequence.
Constraints
- 1 \leq K \lt N \leq 1000
- K is odd.
- A_i is 0 or 1.
Input and Output
This is an interactive task (where your program and the judge interact via Standard Input and Output).
First of all, receive N and K from Standard Input.
N K
Then, repeat asking queries until you can uniquely determine (A_1, A_2, \dots, A_N).
Each query should be printed to Standard Output in the following format, where x_1, x_2, \dots, and x_K are K distinct integers between 1 and N, inclusive.
? x_1 x_2 \dots x_K
The response to the query is given from Standard Input in the following format.
T
Here, T denotes the response to the query.
- T is
0when A_{x_1} + A_{x_2} + \dots + A_{x_K} is even, and - T is
1when A_{x_1} + A_{x_2} + \dots + A_{x_K} is odd.
However, if x_1, x_2, \dots and x_K do not satisfy the constraints, or the number of queries exceeds N, then T is -1.
If the judge returns -1, your program is already considered incorrect, so terminate the program immediately.
When you can determine all the elements of A, print those elements in the following format, and terminate the program immediately.
! A_1 A_2 \dots A_N
Notes
- Print a newline and flush Standard Output at the end of each message. Otherwise, you may get a TLE verdict.
- The verdict will be indeterminate if there is malformed output during the interaction or your program quits prematurely.
- Terminate the program immediately after printing the answer, or the verdict will be indeterminate.
- The judge for this problem is adaptive. This means that the judge may modify the contents of A as long as it is consistent with the responses to the past queries.
Sample Interaction
In the following interaction, N=5 and K=3. Note that the following output itself will result in WA.
Here, A = (1, 0, 1, 1, 0) is indeed consistent with the responses, but so is (0, 0, 1, 0, 0), so sequence A is not uniquely determined. Thus, this program is considered incorrect.
| Input | Output | Description |
|---|---|---|
5 3 | First, you are given integers N and K. | |
? 2 4 1 | You ask a query with (x_1, x_2, x_3) = (2, 4, 1). | |
0 | The response to the query is 0, so the judge returns that value. | |
? 5 3 2 | You ask a query with (x_1, x_2, x_3) = (5, 3, 2). | |
1 | The response to the query is 1, so the judge returns that value. | |
! 1 0 1 1 0 | You print (1, 0, 1, 1, 0) to guess A. Since sequence A is not uniquely determined, the verdict will be WA. |