P13051 [GCJ 2020 Qualification] ESAb ATAd

去年，一个研究联盟在使用分布式数据库系统时遇到了问题，该系统有时会丢失部分数据。不过你不需要理解那个问题就能解决本题！ 该联盟认为分布式系统过于复杂，于是决定将 $\mathbf{B}$ 位重要信息存储在一台超级计算机的单个数组中。为了增加安全性，他们设置了获取信息的障碍：用户必须查询 1 到 $\mathbf{B}$ 之间的位位置，才能获得该位存储的值。 不幸的是，这台超现代计算机会受到随机量子涨落的影响！具体来说，在发送第 1、11、21、31...次查询后（但在返回响应前），量子涨落会以均等概率（各 25%）引发以下四种效应之一： * 数组取反：所有 0 变 1，所有 1 变 0； * 数组反转：第 1 位与第 $\mathbf{B}$ 位交换，第 2 位与第 $\mathbf{B}-1$ 位交换，以此类推； * 同时发生取反和反转（顺序无关）； * 数组保持不变。 每次量子涨落的影响没有任何提示。联盟现在非常担忧，雇佣你来恢复这些珍贵数据（无论它们当前处于何种状态）！你能否找出整个数组，使得你的答案在提交时是准确的？注意：提交答案不算作查询，例如如果你在第 30 次查询后提交答案，数组状态将与第 21-30 次查询期间的状态一致。 ### 交互协议 这是一个交互题。 初始时，你的程序应读取包含两个整数 $\mathbf{T}$ 和 $\mathbf{B}$ 的单行输入：分别表示测试用例数量和数组位数。注意所有测试用例的 $\mathbf{B}$ 相同。 接着处理 $\mathbf{T}$ 个测试用例。每个用例中，评测系统会预设一个 $\mathbf{B}$ 位数组（注意该数组可能因用例而异，且不一定是随机生成的）。你可以进行最多 150 次如下形式的查询： * 你的程序输出 1 到 $\mathbf{B}$ 之间的整数 $\mathrm{P}$，表示要查询的位位置； * 若当前查询次数是第 1、11、21...次（即模 10 余 1），评测系统会随机选择上述四种效应之一（独立于之前的选择）改变数组； * 评测系统返回单字符 0 或 1 表示当前 $\mathrm{P}$ 位的值，若 $\mathrm{P}$ 非法则返回 $\mathrm{N}$。 完成查询后，你必须进行如下最终交互： * 你的程序输出由 $\mathbf{B}$ 个 0/1 组成的字符串，表示当前数组状态（可能与初始状态不同）； * 评测系统返回 $\mathrm{Y}$ 表示答案正确，$\mathrm{N}$ 表示错误（或格式非法）。收到 $\mathrm{Y}$ 后应处理下一个测试用例，若无更多用例则终止程序。 当评测系统返回 $\mathrm{N}$ 后，将不再发送任何输出。若你的程序继续等待会导致超时错误。注意：你需要确保程序及时退出以避免超时错误。若内存超限或运行时错误，将得到相应判果。

参见交互协议。

参见交互协议。

以下交互对应测试集 1： ``` t, b = readline_int_list() // 读取 t=100 和 b=10 // 评测系统初始数组：0001101111（实际测试集 1 不一定使用此数组） printline 1 // 查询第 1 位 flush stdout // 这是第 1 次查询（1 mod 10），系统随机选择取反+反转，数组变为 0000100111 r = readline_chr() // 返回 0 printline 6 // 查询第 6 位 flush stdout // 第 2 次查询（2 mod 10），无量子涨落 r = readline_chr() // 返回 0 ... // 此处省略第 3-10 次查询 ... printline 1 // 再次查询第 1 位 flush stdout // 第 11 次查询（11 mod 10），系统随机选择反转，数组变为 1110010000 r = readline_chr() // 返回 1 printline 1110110000 // 尝试提交错误答案 flush stdout ok = readline_chr() // 返回 N exit // 退出以避免超时错误 ``` 可使用[交互测试工具](https://storage.googleapis.com/coding-competitions.appspot.com/interactive_runner.py)进行本地测试。 **数据范围** $1 \leq \mathbf{T} \leq 100$ **测试集 1（1 分，可见判果）** - $\mathrm{B}=10$ **测试集 2（9 分，可见判果）** - $\mathrm{B}=20$ **测试集 3（16 分，隐藏判果）** - $\mathrm{B}=100$ 翻译由 DeepSeek V3 完成