P6960 [NEERC 2017] Interactive Sort

这是一道 IO 交互题。

Ivan 想和你玩一个游戏。他选取了从 $1$ 到 $n$ 的所有整数，打乱顺序后，将所有偶数放入数组 $e$，所有奇数放入数组 $o$。 你的任务是找出数组 $e$ 和 $o$。 你可以向 Ivan 提出特定类型的问题。每个问题包含两个整数 $i$ 和 $j$。对于每个问题，Ivan 会回答 $e[i] < o[j]$ 是否成立。 你最多可以提出 $300,000$ 个问题。 ## 交互协议 首先，测试系统会输入整数 $n (1 \le n \le 10,000)$ —— Ivan 使用的整数数量。 你的解决方案应输出两种类型的请求： • “? i j”。其中 $1 \le i \le ⌊n/2⌋, 1 \le j \le ⌈n/2⌉$。测试系统会响应符号 $“”$。 • “! $e_1\ e_2\ \cdots e_{⌊n/2⌋}\ o_1\ o_2 \cdots o_{⌈n/2⌉}$” 表示你的程序确定的 $e$ 和 $o$ 的值。 在每次请求后不要忘记刷新输出缓冲区！ 你的解决方案必须恰好发出一次第二种类型的请求，且该请求必须是最后一个请求，并在发出后正常终止。 你的解决方案最多可以发出 $300,000$ 次第一种类型的请求。 每个测试用例的 $n$ 值是固定的，数字使用 Java 内置的洗牌函数（使用固定种子）进行打乱。

无

无

题面翻译由 Deepseek 提供。