← 返回题目列表

Codeforces · 1372/F

F. Omkar 和模式

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

雷丢失了他的阵列,需要通过询问奥姆卡来找到它。 Omkar愿意透露,该阵列具有以下品质:

1. 数组有 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) 个元素。
2. 数组 $$$a_i$$$ 中的每个元素都是 $$$1 \le a_i \le 10^9.$$$ 范围内的整数
3. 数组按非降序排序。

Ray 被允许向 Omkar 发送一系列查询。查询由两个整数 $$$l$$$ 和 $$$r$$$ 组成,使得 $$$1 \le l \le r \le n$$$。 Omkar 将返回两个整数 $$$x$$$ 和 $$$f$$$。 $$$x$$$ 是从索引 $$$l$$$ 到索引 $$$r$$$ 的子数组的众数。数组的众数由出现最频繁的数字定义。如果有多个出现次数最多的数字,则将其中最小的数字视为众数。 $$$f$$$ 是$$$x$$$ 在查询的子数组中出现的次数。

该数组具有 $$$k$$$ ($$$1 \le k \le \min(25000,n)$$$) 个不同元素。然而,由于雷的罪孽,奥姆卡不会告诉雷$$$k$$$是什么。 Ray 最多可以发送 $$$4k$$$ 查询。

帮助雷找到他丢失的阵列。

输入

输入的唯一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$),它等于您要查找的数组的长度。

互动

交互从读取 $$$n$$$ 开始。

然后你可以进行一种类型的查询:

- "$$$? \enspace l \enspace r$$$" ($$$1 \le l \le r \le n$$$) 其中 $$$l$$$ 和 $$$r$$$ 是您要查询的子数组的边界。

每个查询的答案将采用“$$$x \enspace f$$$”的形式,其中 $$$x$$$ 是子数组的众数,$$$f$$$ 是 $$$x$$$ 在子数组中出现的次数。

- $$$x$$$ 满足 ($$$1 \leq x \leq 10^9$$$)。
- $$$f$$$ 满足 ($$$1 \leq f \leq r-l+1$$$)。
- 如果您进行超过 $$$4k$$$ 查询或违反查询中的数字范围,您将得到输出“-1”。
- 如果您在收到响应“$$$-1$$$”后终止,您将得到“错误答案”的判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。

要输出您的答案,请打印:

- "$$$! \enspace a_1 \enspace a_2 \enspace \ldots \enspace a_{n-1} \enspace a_n$$$" 这是一个感叹号,后跟数组,每个元素之间有一个空格。

之后就退出了。此查询不计入 $$$4k$$$ 查询限制。

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

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

黑客格式

要破解,请在第一行输出 $$$1$$$ 整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。在第二行输出 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_{n-1}, a_n$$$ 以空格分隔,这样最多有 $$$25000$$$ 不同的数字,并且 $$$a_j \le a_{j+1}$$$ 对于从 $$$1$$$ 到 $$$n-1$$$ 的所有 $$$j$$$。

示例

输入 #1

6

2 2

2 2

3 2

2 1

输出 #1

? 1 6

? 1 3

? 4 6

? 3 4

! 1 2 2 3 3 4

注意

第一个查询是 $$$l=1$$$ 和 $$$r=6$$$。众数为 $$$2$$$,$$$2$$$ 出现 $$$2$$$ 次,因此 $$$x=2$$$ 且 $$$f=2$$$。请注意,$$$3$$$ 也出现了两次,但输出了$$$2$$$,因为$$$2$$$ 较小。

第二个查询是 $$$l=1$$$ 和 $$$r=3$$$。众数为 $$$2$$$ 且 $$$2$$$ 在索引为 $$$[1,3]$$$ 的子数组中出现两次。

第三个查询是 $$$l=4$$$ 和 $$$r=6$$$。众数为 $$$3$$$ 且 $$$3$$$ 在索引为 $$$[4,6]$$$ 的子数组中出现两次。

第四个查询是$$$l=3$$$ 和$$$r=4$$$。众数为 $$$2$$$,在索引为 $$$[3,4]$$$ 的子数组中出现一次。请注意,$$$3$$$ 在该范围内也出现一次,但 $$$2$$$ 小于 $$$3$$$。