CF1765G Guess the String

这是一个交互式问题。你需要在每输出一行后立即使用刷新操作。例如，在 C++ 中应使用函数 fflush(stdout)，在 Java 或 Kotlin 中应使用 System.out.flush()，在 Python 中应使用 sys.stdout.flush()。 评测机有一个由字符 $0$ 和/或 $1$ 组成的字符串 $s$。该字符串的第一个字符为 $0$。字符串的长度为 $n$。你需要猜出这个字符串。我们用 $s[l..r]$ 表示 $s$ 的第 $l$ 位到第 $r$ 位的子串（即 $s[l..r]$ 表示字符串 $s_ls_{l+1} \dots s_r$）。 字符串 $s$ 的前缀函数定义为数组 $[p_1, p_2, \dots, p_n]$，其中 $p_i$ 是最大的整数 $j \in [0, i-1]$，使得 $s[1..j] = s[i-j+1..i]$。反前缀函数定义为数组 $[q_1, q_2, \dots, q_n]$，其中 $q_i$ 是最大的整数 $j \in [0, i-1]$，使得 $s[1..j]$ 与 $s[i-j+1..i]$ 在每一位都不同。 例如，对于字符串 011001，其前缀函数为 $[0, 0, 0, 1, 1, 2]$，反前缀函数为 $[0, 1, 1, 2, 3, 4]$。 你可以通过以下两种类型的询问来猜测字符串 $s$： - $1\ i$ —— “$p_i$ 的值是多少？” - $2\ i$ —— “$q_i$ 的值是多少？” 你需要在不超过 $789$ 次询问的情况下猜出字符串。注意，提交答案不计入询问次数。 在每个测试和每个测试用例中，字符串 $s$ 都是预先固定的。

评测机首先发送一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。 在每个测试用例开始时，评测机发送一个整数 $n$（$2 \le n \le 1000$），表示字符串的长度。 之后，你的程序可以通过输出以下任意一行向评测机发起询问（每输出一行后请立即刷新输出）： - $1\ i$ —— 询问“$p_i$ 的值是多少？” - $2\ i$ —— 询问“$q_i$ 的值是多少？” 对于每次询问，评测机会在单独一行输出一个整数。可能的情况有： - 如果询问合法且未超过当前测试用例的询问次数限制，则输出该询问的答案； - 如果询问不合法（例如 $1 \le i \le n$ 不满足）或当前测试用例的询问次数已超限，则输出 $-1$。 提交答案时，你的程序应输出如下格式的一行（输出后请立即刷新输出）： - $0\ s$，其中 $s$ 是一个长度为 $n$ 的仅包含 $0$ 和/或 $1$ 的字符串。 如果你的猜测正确，评测机会在单独一行输出整数 $1$，表示你可以进入下一个测试用例（或如果是最后一个测试用例则程序应终止），并且你的询问次数会被重置。如果猜测不正确，评测机会输出 $-1$。 如果你的程序收到 $-1$ 作为回答，应立即终止程序。否则你的提交将被判为“Wrong Answer”。如果程序未终止，提交的判题结果将不可预期。

见输入格式说明。

示例中展示了 $t=2$ 时的一种可能的交互方式，评测机的字符串分别为 011001 和 00111。注意，所有 // 后的内容为注释，仅用于解释交互含义，实际评测机不会输出这些注释，你的程序也不应输出。空行仅为方便阅读，实际评测机不会输出空行，你的程序也不应输出空行。 由 ChatGPT 4.1 翻译