AT_ttpc2024_1_i Near Pair
题目描述
这是一道交互式问题，你的程序需要与评测系统通过输入输出进行对话。
你将得到整数 $N, K, Q$，评测系统会隐藏一个排列 $(a_1, a_2, \ldots, a_N)$，该排列是 $1$ 到 $N$ 的一种排列方式。你可以最多询问 $Q$ 次，每次询问的过程如下：
- 你需要选择集合 $\{1, 2, \ldots, N\}$ 的一个子集 $S$。然后询问子集 $S$ 中有多少对不同的二元组 $(i, j)$ 满足 $i < j$ 且 $|a_i - a_j| \leq K$。
设 $a_t = 1$ 时对应的 $t$ 为 $x$，$a_t = N$ 时对应的 $t$ 为 $y$，你需要找出集合 $\{x, y\}$。不必区分哪一个是 $x$，哪一个是 $y$。
请注意，评测系统在整个交互过程中保持排列 $(a_1, a_2, \ldots, a_N)$ 不变。
### 输入格式
这是一个交互式问题。
首先，你需要从标准输入读取三个整数 $N, K, Q$。
> $N$ $K$ $Q$
接着，你需要不断提问，直到确定集合 $\{x, y\}$。
每次提问需要按照以下格式输出到标准输出：
> ? $s_1 s_2 \ldots s_N$
其中，$s_1 s_2 \ldots s_N$ 是一个表示子集 $S$ 的字符串，长度为 $N$。如果 $i$ 在子集 $S$ 中，则 $s_i = \texttt{1}$，否则 $s_i = \texttt{0}$。
对于每次提问，评测系统会返回如下格式的响应：
> $T$
其中，$T$ 是满足条件的二元组数量。
当你找到集合 $\{x, y\}$ 后，请按照以下格式输出这两个数字，并立即结束程序：
> ! $x$ $y$
### 数据范围与提示
- 所有输入均为整数。
- $N = 20000$
- $1 \leq K \leq 10$
- $Q = 30(K + 1)$
#### 部分分数
如果在满足 $K = 10$ 的数据集上正确解答，将获得 30 分。
### 注意事项
- **每次输出后，请务必在末尾添加换行符并刷新标准输出，否则可能会导致超时（TLE）。**
- 如果问询格式有误或问询次数超限，评测系统的响应将为 $T = -1$。在此情况下，请立即结束程序，否则可能导致超时（TLE）。
- 请注意，多余的换行符会被视为格式错误的输出。
### 输入输出示例
以下是一个示例，其中 $N = 5, K = 2, Q = 90$。注意，该示例不符合输入约束，因此不会作为测试用例的一部分。
```
输入 输出 说明
5 2 90 ? 11000 评测系统隐藏了排列 (3, 5, 2, 1, 4)
1 询问 $S = \{1, 2\}$，只有组合 $(1, 2)$ 符合条件。
? 10011 询问 $S = \{1, 4, 5\}$
2 组合 $(1, 4)$ 和 $(1, 5)$ 符合条件。
! 2 4 输出答案 $\{2, 4\}$，因为 $a_4 = 1$ 且 $a_2 = N$。
```
**本翻译由 AI 自动生成**
输入格式
无
输出格式
无
说明/提示
### 部分点
追加の制約 $ 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) $