← 返回题目列表

Codeforces · 1556/D

D. 猜猜看

中文机器翻译题面 查看原题

这是一个交互式任务

William 脑子里有一个特定的整数序列 $$$a_1, a_2, \dots, a_n$$$,但出于安全考虑,他不想完全透露给你。 William 准备回答不超过 $$$2 \cdot n$$$ 的以下问题:

- 索引为 $$$i$$$ 和 $$$j$$$ 的两个项目按位 AND 的结果是什么 ($$$i \neq j$$$)
- 索引为 $$$i$$$ 和 $$$j$$$ 的两个项目按位或的结果是什么 ($$$i \neq j$$$)

你可以问 William 这些问题,你需要找到序列中第 $$$k$$$ 个最小的数字。

形式上,第 $$$k$$$ 个最小数字等于按非降序排序的 1 索引数组中第 $$$k$$$ 个位置的数字。例如,在数组$$$[5, 3, 3, 10, 1]$$$ $$$4$$$中,第一个最小的数字等于$$$5$$$,而$$$2$$$nd和$$$3$$$rd是$$$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$$$ 问题(不包括“完成”操作)。

输出的每一行可能属于以下类型之一:

- "or i j" $$$(1 \le i, j \le n, i \neq j)$$$,其中 $$$i$$$ 和 $$$j$$$ 是要计算按位 OR 的项目的索引。
- "and i j" $$$(1 \le i, j \le n, i \neq j)$$$,其中 $$$i$$$ 和 $$$j$$$ 是要计算按位 AND 的项目的索引。
- “完成 res”,其中 $$$res$$$ 是序列中第 $$$k$$$ 个最小的数字。输出此行后,程序执行必须结束。

响应前两种类型的查询,您将得到一个整数$$$x$$$,即您所选择的数字的运算结果。

输出一行后,不要忘记输出新行字符并刷新输出缓冲区。否则您将收到“超出空闲限制”的信息。要刷新缓冲区,请使用:

- C++ 中的 fflush(stdout)
- Java 中的 System.out.flush()
- Python 中的 stdout.flush()
- 帕斯卡刷新(输出)
- 对于其他语言,请参阅文档

如果您执行了错误的查询,则响应将为 $$$-1$$$。收到响应 $$$-1$$$ 后,您必须立即停止程序才能收到“错误答案”的判决。

黑客攻击

要执行黑客攻击,您需要使用以下格式:

第一行必须包含两个整数 $$$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

7 6

2

7

输出 #1

and 2 5

or 5 6

finish 5

注意

在示例中,隐藏序列为 $$$[1, 6, 4, 2, 3, 5, 4]$$$。

下面是示例中的交互。

查询(参赛者程序)响应(互动者)注释和2 52$$$a_2=6$$$,$$$a_5=3$$$。交互器返回给定数字的按位与。或 5 67$$$a_5=3$$$, $$$a_6=5$$$。交互器返回给定数字的按位或。完成 5$$$5$$$ 是正确答案。请注意,您必须找到该值,而不是第 k 个最小数字的索引。