AT_1_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 自动生成