#SYUCT13J. 深空回声

深空回声

题目描述

深空探测器“远眺一号”的内存中保存着一个长度为 nn 的二进制串

S=s1s2⋯sn,si∈{0,1}.S=s_1s_2\cdots s_n,\qquad s_i\in\{0,1\}.

巡检确认,SS 中恰好有 KK 个字符 1,即

∑i=1nsi=K.\sum_{i=1}^{n}s_i=K.

地面站的任务是还原出原始串 SS。

地面站的深空天线只能发送长度恰好为 nn 的二进制对照串

T=t1t2⋯tn,ti∈{0,1}.T=t_1t_2\cdots t_n,\qquad t_i\in\{0,1\}.

探测器会返回 SS 与 TT 的汉明距离

$$d(S,T)=\left|\left\{i\mid 1\le i\le n,\ s_i\ne t_i\right\}\right|.$$

返回的是完整的距离数值,而不是距离的奇偶性。

你的程序需要在最多 3434 次询问内还原出原始串 SS。

交互流程

  1. 交互器首先向你的程序输出一行两个整数 nn 和 KK(2≤n≤655362 \le n \le 65536,1≤K≤21 \le K \le 2),用空格分隔。
  2. 每次询问,你的程序向交互器输出一行 ? T,其中 TT 是一个长度为 nn 的 0/1 串;交互器回复一行一个整数 dd(0≤d≤n0 \le d \le n),表示 SS 与 TT 的汉明距离。
  3. 询问次数不能超过 3434 次。若你发起第 3535 次询问,交互器会回复一行 -1 并终止交互;此时你的程序必须立即正常退出,任何后续读写都可能导致判题失败。
  4. 当你确定 SS 后,输出一行 ! S,其中 SS 是你还原的长度为 nn 的 0/1 串,然后正常退出,无需等待任何回复。

注意事项

  • 每次输出后必须立即刷新输出缓冲区。C++ 使用 std::endl 或 fflush(stdout) 均可。
  • 交互器是非自适应的:SS 在交互开始前就已经确定,不会随你的询问而改变。
  • 若你的任何一行输出不符合上述格式(前缀标记、长度、字符集),交互器会立即判定你的输出错误并终止交互。
  • 本题仅支持 C++(GNU g++20)提交。

输入格式

第一行,交互器向你输出两个整数 nn(2≤n≤655362 \le n \le 65536)和 KK(1≤K≤21 \le K \le 2),用空格分隔。

随后,每当且仅当你发出一次格式合法的询问时,交互器会输出一行一个整数 dd(0≤d≤n0\le d\le n)。若你超出询问次数上限,交互器输出 -1 后终止交互。

输出格式

  • 每次询问输出一行 ? T;
  • 确定答案后输出一行 ! S;
  • 询问次数不得超过 3434 次;
  • 每次输出后必须立即刷新输出缓冲区。

提示

下面是一次合法交互示例,其中 n=4n=4、K=2K=2、S=S= 0110:

(交互器输出)4 2
(你的输出)  ? 0000
(交互器输出)2
(你的输出)  ? 1111
(交互器输出)2
(你的输出)  ? 1000
(交互器输出)3
(你的输出)  ! 0110

这段记录只用于展示一次格式合法且最终答案正确的交互过程;前三次询问本身并不能唯一确定隐藏串,不应视为完整求解算法。

设 c(m)c(m) 表示 SS 的前 mm 位中字符 1 的数量。若发送的对照串 TT 满足前 mm 位为 1、其余位为 0,则返回的距离满足

d=K+m−2c(m).d=K+m-2c(m).

因此可以由 dd 计算 c(m)c(m)。更一般地,若把任意位置集合 BB 中的位设为 1,其余位设为 0,也可以由返回的汉明距离计算 BB 中字符 1 的数量。

下载正式赛最终版 PDF 题面