← 返回题目列表

Codeforces · 1486/C2

C2. 猜最伟大(困难版)

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

简单版和困难版之间的唯一区别是查询数量的限制。

这是一个交互问题。

存在一个由 $$$n$$$ 不同数字组成的数组 $$$a$$$。在一个查询中,您可以询问子段 $$$a[l..r]$$$ 中第二个最大元素的位置。在不超过 20 次查询中找到数组中最大元素的位置。

子段 $$$a[l..r]$$$ 是所有元素 $$$a_l, a_{l + 1}, ..., a_r$$$。询问该子段后,您将获得该子段在整个数组中的第二个最大值的位置。

输入

第一行包含一个整数 $$$n$$$ $$$(2 \leq n \leq 10^5)$$$ — 数组中的元素数量。

互动

您可以通过打印“? $$$l$$$ $$$r$$$” $$$(1 \leq l < r \leq n)$$$ 来提出查询。答案是所有元素 $$$a_l, a_{l + 1}, ..., a_r$$$ 的第二个最大值的索引。数组 $$$a$$$ 是预先固定的,在交互时不能更改。

可以通过打印“!$$$p$$$”来输出答案,其中$$$p$$$是数组中最大元素的索引。

您最多可以提出 20 个疑问。打印答案不算作查询。

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

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

黑客

要进行破解,请使用以下测试格式。

在第一行输出一个整数 $$$n$$$ $$$(2 \leq n \leq 10^5)$$$。在第二行中输出 $$$n$$$ 整数 $$$1$$$ 到 $$$n$$$ 的排列。 $$$n$$$在排列中的位置就是最大值的位置

示例

输入 #1

5

3

4

输出 #1

? 1 5

? 4 5

! 1

注意

在示例中,假设 $$$a$$$ 为 $$$[5, 1, 4, 2, 3]$$$。因此,在询问$$$[1..5]$$$子段$$$4$$$之后,它是第二个最大值,它的位置是$$$3$$$。询问 $$$[4..5]$$$ 子段 $$$2$$$ 是第二个最大值,它在整个数组中的位置是 $$$4$$$。

请注意,还有其他数组 $$$a$$$ 会产生相同的交互,并且它们的答案可能不同。给出示例输出是为了理解交互。