AT_ttpc2024_1_i Near Pair

この問題は **インタラクティブな問題**（あなたの作成したプログラムとジャッジシステムが入出力を介して対話を行う形式の問題）です。 整数 $ 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 $ 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 ! $ x $ $ y $ ### 注意点 - **出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。** - 質問の形式が間違っている場合、および、質問回数を超過した場合、ジャッジの応答は $ T = -1 $ となります。これを受け取った場合、ただちにプログラムを終了してください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。 - 余計な改行は不正なフォーマットの出力とみなされることに注意してください。

N/A

N/A

### 部分点 追加の制約 $ K = 10 $ を満たすデータセットに正解した場合は $ 30 $ 点が与えられる。 ### 注意点 - **出力を行うたびに、末尾に改行を入れて標準出力を 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 $ であるので、この出力は正解です。 ### Constraints - 入力はすべて整数 - $ N = 20000 $ - $ 1 \leq K \leq 10 $ - $ Q = 30(K + 1) $