CF1556D Take a Guess

这是一个交互题。 William 心中有一个整数序列 $a_1, a_2, \dots, a_n$，但出于安全考虑，他不想完全透露给你。William 准备回答你不超过 $2 \cdot n$ 个如下类型的问题： - 给定两个下标 $i$ 和 $j$（$i \neq j$），这两个数的按位与（bitwise AND）结果是多少？ - 给定两个下标 $i$ 和 $j$（$i \neq j$），这两个数的按位或（bitwise OR）结果是多少？ 你可以向 William 提出这些问题，你需要找出该序列的第 $k$ 小的数。 形式化地说，第 $k$ 小的数是指将数组按非递减顺序排序后，位于第 $k$ 个位置（从 1 开始计数）的数。例如，在数组 $[5, 3, 3, 10, 1]$ 中，第 $4$ 小的数是 $5$，第 $2$ 小和第 $3$ 小的数都是 $3$。

保证序列中每个元素都满足 $0 \le a_i \le 10^9$。

第一行给出两个整数 $n$ 和 $k$，$3 \le n \le 10^4, 1 \le k \le n$，分别表示序列 $a$ 的长度和你需要找的第 $k$ 小的数。 之后，你可以最多询问 $2 \cdot n$ 个问题（不包括“finish”操作）。 你的每一行输出可以是以下三种类型之一： - "or i j"（$1 \le i, j \le n, i \neq j$），表示你想询问下标为 $i$ 和 $j$ 的数的按位或。 - "and i j"（$1 \le i, j \le n, i \neq j$），表示你想询问下标为 $i$ 和 $j$ 的数的按位与。 - "finish res"，其中 $res$ 是该序列的第 $k$ 小的数。输出这一行后，程序必须立即结束。 对于前两种类型的询问，你会得到一个整数 $x$，表示你所选的两个数的运算结果。 每输出一行后，不要忘记输出换行符并刷新输出缓冲区。否则你会收到“Idleness limit exceeded”的提示。刷新缓冲区的方法如下： - C++：fflush(stdout) - Java：System.out.flush() - Python：stdout.flush() - Pascal：flush(output) - 其它语言请参考相关文档 如果你进行了错误的询问，返回值将为 $-1$。收到 $-1$ 后，你必须立即终止程序，否则会收到“Incorrect answer”的判定。 Hack 格式 进行 hack 时，输入格式如下： 第一行包含两个整数 $n$ 和 $k$，$3 \le n \le 10^4, 1 \le k \le n$，分别表示序列 $a$ 的长度和你需要找的第 $k$ 小的数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，$0 \le a_i \le 10^9$，表示序列 $a$。

在示例中，隐藏的序列为 $[1, 6, 4, 2, 3, 5, 4]$。 下面是示例中的交互过程： | 询问（选手程序） | 回答（交互器） | 说明 | |:----------------:|:--------------:|:-----| | and 2 5 | 2 | $a_2=6$，$a_5=3$。交互器返回这两个数的按位与。 | | or 5 6 | 7 | $a_5=3$，$a_6=5$。交互器返回这两个数的按位或。 | | finish 5 | | $5$ 是正确答案。注意你需要输出的是第 $k$ 小的数的值，而不是下标。 | 由 ChatGPT 4.1 翻译