← 返回题目列表

Codeforces · 2163/D1

D1. Diadrash(简单版)

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

这是问题的简单版本。版本之间的区别在于,在此版本中,您最多可以进行 $$$\max(300, \lceil\frac{n}{2}\rceil+2)$$$ 查询。只有解决了该问题的所有版本,您才能破解。

这个问题是交互式的。

有一个从 $$$0$$$ 到 $$$n-1$$$ 的整数排列$$$^{\text{*}}$$$ $$$p$$$ 对你隐藏。此外,还给出了 $$$q$$$ 范围 $$$[l_1, r_1], [l_2, r_2], \ldots, [l_q, r_q]$$$,其中 $$$1 \le l_i \le r_i \le n$$$。

您需要在输入中为您提供的 $$$q$$$ 范围内的 $$$p$$$ 值中找出最大 $$$\operatorname{MEX}$$$。形式上,您必须发现 $$$\max _{i=1}^q {\operatorname{MEX}([p_{l_i}, p_{l_i+1}, \ldots, p_{r_i}])}$$$$$$^{\text{†}}$$$ 的值。为此,您最多可以进行以下形式的 $$$\max(300, \lceil\frac{n}{2}\rceil+2)$$$ 查询:

  • 选择 任何 两个整数 $$$1 \le l \le r \le n$$$,您将收到值 $$$\operatorname{MEX}([p_{l}, p_{l+1}, \ldots, p_{r}])$$$。

$$$^{\text{*}}$$$从$$$0$$$到$$$n-1$$$的整数排列是$$$n$$$元素的序列,其中从$$$0$$$到$$$n-1$$$的每个整数只出现一次。例如,序列 $$$[0, 3, 1, 2]$$$ 是一个排列,但序列 $$$[0, 0, 2, 1]$$$ 不是。

$$$^{\text{†}}$$$序列的 $$$\operatorname{MEX}$$$ 被定义为未出现在该序列中的最小非负整数。例如,$$$\operatorname{MEX}([0, 0, 1, 3]) = 2$$$ 和 $$$\operatorname{MEX}([1, 2, 2]) = 0.$$$

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。

每个测试用例的第一行恰好包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$4 \le n \le 10^4$$$, $$$1 \le q \le 3 \cdot 10^5$$$) - 分别是排列的大小和范围的数量。

接下来的 $$$q$$$ 行的第 $$$i$$$ 行包含两个整数 $$$l_i, r_i$$$ ($$$1 \le l_i \le r_i \le n$$$)。

保证所有测试用例中 $$$n$$$ 和 $$$q$$$ 的总和分别不超过 $$$10^4$$$ 和 $$$3 \cdot 10^5$$$。

附加限制: 保证同一测试用例中没有重复的范围。

互动

要提出查询,请按以下格式输出一行(不带引号):

  • "? $$$l$$$ $$$r$$$" ($$$1 \le l \le r \le n$$$)

陪审团将返回一个整数,即 $$$\operatorname{MEX}([p_{l}, p_{l+1}, \ldots, p_{r}])$$$ 的值。

找到答案后,按以下格式输出一行:

  • "! $$$x$$$" ($$$0 \le x \le n$$$)。

之后,继续处理下一个测试用例,如果是最后一个测试用例则终止程序。打印答案不算作查询。

交互器是 不 自适应,意味着在参与者提出查询之前排列的值是已知的。

如果您的程序进行超过 $$$\max(300, \lceil\frac{n}{2}\rceil+2)$$$ 查询,您的程序应立即终止以接收判决 错误答案。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。

打印查询后,不要忘记输出行尾并刷新输出。否则,您可能会得到 超出空闲限制 判决。为此,请使用:

  • fflush(标准输出) or cout.flush() 在 C++ 中
  • System.out.flush() 在 Java 中;
  • 冲洗(输出) 帕斯卡;
  • stdout.flush() 在 Python 中;
  • 请参阅其他语言的文档。

黑客

对于 hack,请使用以下格式。

输入的第一行应包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。

每个测试用例的第一行应包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$4 \le n \le 10^4$$$, $$$1 \le q \le 3\cdot 10^5$$$) - 分别是排列的大小和给定的范围数。

第二行应包含 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$ — 其中 $$$p_i$$$ 是排列的第 $$$i$$$ 个元素。它应该认为 $$$p$$$ 是包含整数 $$$0$$$ 到 $$$n-1$$$ 的排列。

接下来的 $$$q$$$ 行的第 $$$i$$$ 行应包含两个整数 $$$l_i$$$、$$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$)。

在所有测试用例中,$$$n$$$ 和 $$$q$$$ 的总和分别不超过 $$$10^4$$$ 和 $$$3 \cdot 10^5$$$。

附加限制: 在同一测试用例中不应重复任何范围。

示例

输入
复制

3
4 3
1 2
2 4
1 3

2

0

1

4

6 6
1 2
2 4
3 3
4 6
5 5
6 6

6

1

2

4 4
1 1
2 2
3 3
4 4

输出
复制






? 1 3

? 4 4

? 1 1

? 1 4

! 2







? 1 6

? 3 3

? 2 4

! 2





! 1

注意

在第一个示例中,隐藏排列为 $$$p = [0, 3, 1, 2]$$$,范围为 $$$[1, 2], [2, 4], [1, 3]$$$。第三个范围是最佳的,因为 $$$\operatorname{MEX}([p_1, p_2, p_3]) = \operatorname{MEX}([0, 3, 1]) = 2$$$,这是最大值。

在我们的第一个查询中,我们询问 $$$l = 1, r = 3$$$,法官给出值 $$$\operatorname{MEX}([p_1, p_2, p_3]) = 2$$$。在第二个查询中,我们询问 $$$l = 4, r = 4$$$,法官给出值 $$$\operatorname{MEX}([p_4]) = 0$$$。同样,$$$\operatorname{MEX}([p_1]) = 1$$$ 和 $$$\operatorname{MEX}([p_1, p_2, p_3, p_4]) = 4$$$。

不知何故,我们发现我们正在寻找的答案是$$$2$$$。

在第二个示例中,$$$p = [3, 5, 0, 1, 4, 2]$$$。

在第三个示例中,$$$p = [0, 1, 2, 3]$$$。

请注意,这只是交互工作方式的解释,并不显示解决问题的任何策略。