CF1562F Tubular Bells

你知道管钟是什么吗？它是一种由圆柱形金属管组成的乐器。在管弦乐队中，管钟常用于模拟钟声。 Mike 也有一套管钟！这套管钟由 $n$ 根管子组成，每根管子的长度都是一个从 $l$ 到 $r$ 的整数（包含 $l$ 和 $r$）。显然，所有管子的长度都不相同（制作相同长度的管子没有意义）。已知 $r-l+1=n$。 形式化地说，Mike 的管钟可以用一个长度为 $n$ 的排列 $a$ 描述，$a$ 包含了从 $l$ 到 $r$ 的所有整数，其中 $a_i$ 表示第 $i$ 根管子的长度。 现在有一个有趣的任务：猜出 Mike 的乐器是什么样子的。简单来说，你需要猜出这个排列。 Mike 不会告诉你 $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$ 的最小公倍数。 请解决 Mike 的问题！

每个测试点包含多个测试用例。 第一行包含一个正整数 $t$（$1 \le t \le 20$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的一行包含一个正整数 $n$（$3 \le n \le 10^5$）——Mike 的管钟的管子数量。还满足 $1 \le l \le r \le 2 \times 10^5$，即所有管子的长度不超过 $2 \times 10^5$。 保证所有测试用例的最大查询次数之和（即 $n+5000$ 的总和）不超过 $10^5+5000$。也就是说，所有 $n$ 的总和不超过 $10^5+5000-t \times 5000$。

对于每组输入数据，读入一个整数 $n$。你最多可以进行 $n+5000$ 次查询。 如果你要进行一次查询，输出格式为 "? $x$ $y$"，其中 $x$ 和 $y$ 是你想要了解其长度最小公倍数的两根管子的编号。注意必须满足 $1 \le x, y \le n, x \neq y$。交互器会返回一个整数——你查询的答案。 如果你准备好输出答案，输出格式为 "! $a_1$ $a_2$ ... $a_n$"。输出答案不计入查询次数。 每次查询和输出答案后，别忘了换行并刷新输出缓冲区。否则你会收到 "Idleness limit exceeded" 的判定。刷新缓冲区的方法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。 注意，交互器是非自适应的。也就是说，原始排列在一开始就固定，不会根据你的查询发生变化。 Hack 格式： Hack 时请使用如下格式： 第一行包含一个正整数 $t$（$1 \le t \le 20$）——输入数据集的数量。每组数据集的描述如下。 每个测试用例的第一行包含一个正整数 $n$（$3 \le n \le 10^5$）——管子的数量。已知 $1 \le l \le r \le 2 \times 10^5$，即所有管子的长度不超过 $2 \times 10^5$。 每个测试用例的第二行包含一个长度为 $n$ 的数组 $a$，表示每组数据集中每根管子的长度。记住 $l \le a_i \le r$ 且 $r-l+1=n$，并且所有 $a_i$ 互不相同。

由 ChatGPT 4.1 翻译