I - Near Pair 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

Score: 100 points

Problem Statement

This is an interactive problem, where your program interacts with the judge system via Standard Input and Output.

You are given integers N, K, and Q.
The judge holds a hidden permutation (a_1, a_2, \dots, a_N) of (1, 2, \dots, N).
You may ask up to Q queries to the judge, where each query is as follows:

  • Choose a subset S from \lbrace 1, 2, \dots, N \rbrace. The judge will return the number of distinct pairs (i, j) such that i < j and |a_i - a_j| \leq K where i, j \in S.

Let x be the index t where a_t = 1, and y be the index t where a_t = N. Your task is to identify the set \lbrace x, y \rbrace. (You do not need to distinguish which is x and which is y.)

The judge is non-adaptive, that means the permutation (a_1, a_2, \dots, a_N) is fixed before any interaction begins.

Constraints

  • All input values are integers.
  • N = 20000
  • 1 \leq K \leq 10
  • Q = 30(K + 1)

Partial Score

30 points will be awarded for passing the test set satisfying the additional constraint K = 10.

Input and Output

This is an interactive problem.

First, read integers N, K, and Q from the Standard Input:

N K Q

Then, repeat the following process until you identify the set \lbrace x, y \rbrace:

For a query, output the following format to the Standard Output:

? s_1s_2 \dots s_N

Here, s_1 s_2 \dots s_N is a binary string of length N representing the subset S, where s_i = {}1 if i \in S, and s_i = {}0 otherwise.

The response to your query will be provided in the Standard Input in the following format:

T

Here, T is the answer to the query, representing the number of distinct pairs (i, j) such that i < j and |a_i - a_j| \leq K where i, j \in S.

Once you identify the set \lbrace x, y \rbrace, output the two elements in the following format (order does not matter) and terminate your program immediately:

! x y

Notes

  • Print a newline and flush Standard Output at the end of each message. Otherwise, you may get a TLE verdict.
  • If your query format is invalid or you exceed the number of queries, the judge will respond with T = -1. If you receive this response, you should immediately terminate your program. Otherwise, you may get a TLE verdict.
  • Beware that unnecessary newlines are considered as malformed.

Sample Interaction

The following is a sample interaction for N = 5, K = 2, Q = 90. Note that this example does not meet the constraints and will not appear in the test cases.

Input Output Explanation
The judge holds the permutation (3, 5, 2, 1, 4).
5 2 90 First, integers N, K, and Q are provided.
? 11000 You query with S = \lbrace 1, 2 \rbrace.
1 Only the pair (1, 2) satisfies the condition, so the judge responds with 1.
? 10011 You query with S = \lbrace 1, 4, 5 \rbrace.
2 The pairs (1, 4) and (1, 5) satisfy the condition, so the judge responds with 2.
! 2 4 You output \lbrace 2, 4 \rbrace as the answer. Since a_4 = 1 and a_2 = N, this output is correct.

配点 : 100 点

問題文

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

整数 N, K, Q が与えられます。 ジャッジシステムは (1, 2, \dots, N) の順列 (a_1, a_2, \dots, a_N) を隠し持っています。 あなたはジャッジに Q 回まで次のような質問をすることが出来ます。

  • \lbrace 1, 2, \dots, N \rbrace の部分集合 S を選ぶ。S の異なる 2 元の組 (i,j) であって、 i<j かつ |a_i-a_j|\leq K であるような組の個数を聞く。

a_t=1 となるような t を x とし、 a_t=N となるような t を y とします。 集合 \lbrace x,y \rbrace を特定してください。（どちらが x でどちらが y かを特定する必要はありません。）

なお、ジャッジは適応的 (adaptive) ではなく、順列 (a_1, a_2, \dots, a_N) はやりとりの前から固定されています。

制約

  • 入力はすべて整数
  • N = 20000
  • 1 \leq K \leq 10
  • Q = 30(K + 1)

部分点

追加の制約 K = 10 を満たすデータセットに正解した場合は 30 点が与えられる。

入出力

この問題はインタラクティブな問題です。

最初に、整数 N,K,Q を標準入力から受け取ってください。

N K Q

次に、集合 \lbrace x, y \rbrace を特定できるまで質問を繰り返してください。

質問は、以下の形式で標準出力に出力してください。

? s_1s_2 \dots s_N

ここで、s_1 s_2 \dots s_N は部分集合 S を表す長さ N の文字列で、i \in S ならば s_i = {}1、i \notin S ならば s_i = {}0 としてください。

これに対する応答は、以下の形式で標準入力から与えられます。

T

ここで、T は質問に対する答えで、S の異なる 2 元の組 (i,j) であって、 i<j かつ |a_i-a_j|\leq K であるような組の個数を表します。

答えとなる集合 \lbrace x, y \rbrace を特定出来たら、特定した 2 つの要素を以下の形式で出力してください。（順番はどちらが先でも構いません。）その後、ただちにプログラムを終了してください。

! x y

注意点

  • 出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。
  • 質問の形式が間違っている場合、および、質問回数を超過した場合、ジャッジの応答は T = -1 となります。これを受け取った場合、ただちにプログラムを終了してください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。
  • 余計な改行は不正なフォーマットの出力とみなされることに注意してください。

入出力例

以下は N = 5, K = 2, Q = 90 の場合の入出力例です。この例は入力の制約を満たさないので、テストケースには含まれないことに注意してください。

入力 出力 説明
ジャッジは順列 (3, 5, 2, 1, 4) を隠し持っています。
5 2 90 まず整数 N,K,Q が与えられます。
? 11000 S = \lbrace 1, 2 \rbrace として質問を行います。
1 組 (1, 2) のみが条件を満たすので、標準入力に 1 が与えられます。
? 10011 S = \lbrace 1, 4, 5 \rbrace として質問を行います。
2 (1, 4) と (1, 5) の 2 組が条件を満たすので、標準入力に 2 が与えられます。
! 2 4 答えとして \lbrace 2, 4 \rbrace を出力します。a_4 = 1 かつ a_2 = N であるので、この出力は正解です。