← 返回题目列表

Codeforces · 1562/F

F. 管状钟

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

你知道什么是管钟吗?它们是一种由圆柱形金属管制成的乐器。在管弦乐队中,管钟用于模仿钟声。

迈克也有管铃!它们由 $$$n$$$ 管组成,每个管的长度可以用从 $$$l$$$ 到 $$$r$$$(含)的整数表示。很明显,所有管子的长度都是不同的(制造相同的管子是没有意义的)。还已知 $$$r-l+1 = n$$$。

正式地,我们可以说 Mike 的管钟是通过长度为 $$$n$$$ 的排列 $$$a$$$ 来描述的,其中包含从 $$$l$$$ 到 $$$r$$$ 的所有数字,其中 $$$a_i$$$ 表示第 $$$i$$$ 管的长度。

为您提供了一项有趣的任务:猜测迈克的乐器是什么样子。简单地说,您必须猜测排列。

迈克不会告诉你$$$l$$$ 或$$$r$$$。他只会告诉您 $$$n$$$,并且允许您提出不超过 $$$n + 5000$$$ 的查询。

在每个查询中,您命名两个正整数 $$$x$$$、$$$y$$$,使得 $$$1 \le x, y \le n, x \neq y$$$。对于这个查询,Mike 编写的程序将给出 $$$\mathrm{lcm}(a_x, a_y)$$$,其中 $$$\mathrm{lcm}(c,d)$$$ 表示 $$$c$$$ 和 $$$d$$$ 的最小公倍数。

解决迈克的问题!

输入

每个测试包含多个测试用例。

第一行包含一个正整数$$$t$$$ ($$$1 \le t \le 20$$$),表示测试用例的数量。测试用例的描述如下。

每个测试用例的单行包含一个正整数 $$$n$$$ ($$$3 \le n \le 10^5$$$) — Mike 管钟中的管子数量。另外$$$1 \le l \le r \le 2 \cdot 10^5$$$,即管子的长度不超过$$$2 \cdot 10^5$$$。

保证所有测试用例的最大查询数(即$$$n + 5000$$$)总和不超过$$$10^5 + 5000$$$。这意味着 $$$n$$$ 的总和不超过 $$$10^5 + 5000 - t \cdot 5000$$$。

互动

对于每组输入数据,读取一个整数$$$n$$$。您最多可以进行 $$$n + 5000$$$ 查询。

如果您想进行查询,请以“? $$$x$$$ $$$y$$$”格式输出,其中 $$$x$$$ 和 $$$y$$$ - 您了解其长度的 lcm(最小公倍数)的管数。注意$$$1 \le x, y \le n, x \neq y$$$ 必须满足。交互器将返回一个整数——您的查询的答案。

如果您准备好打印答案,请以“! $$$a_1$$$ $$$a_2$$$ ... $$$a_n$$$”格式打印。答案的输出不被视为查询,并且不包含在查询数中。

每次查询和答案输出后,不要忘记输出行翻译并重置输出缓冲区。否则,您将得到“超出空闲限制”的判决。要重置缓冲区,请使用:

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

请注意,交互器不具有自适应性。也就是说,原始排列在开始时是固定的,不依赖于您的查询。

黑客:

使用以下格式进行黑客攻击:

第一行包含一个正整数 $$$t$$$ ($$$1 \le t \le 20$$$) — 输入数据集的数量。下面给出输入数据集的描述。

每个测试用例的第一行包含一个正整数 $$$n$$$ ($$$3 \le n \le 10^5$$$) — 管数。已知$$$1 \le l \le r \le 2 \cdot 10^5$$$,即管的长度不超过$$$2 \cdot 10^5$$$。

每个测试用例的第二行包含一个由 $$$n$$$ 正整数组成的数组 $$$a$$$ — 每个输入数据集中的管子长度。请记住 $$$l \le a_i \le r$$$ 和 $$$r-l+1 = n$$$,并且所有 $$$a_i$$$ 都是不同的。

示例

输入 #1

3
5
8 10 7 6 9
5
24 25 28 27 26
7
1 2 3 4 5 6 7

输出 #1

? 1 2
40
? 2 5
90
? 3 1
56
? 4 5
18
! 8 10 7 6 9
? 1 5
312
? 2 4
675
! 24 25 28 27 26
? 1 4
4
? 2 5
10
? 3 7
21
? 6 2
6
? 2 5
10
? 1 2
2
? 1 2
2
? 1 2
2
? 1 2
2
? 1 2
2
! 1 2 3 4 5 6 7