P13636 [NWRRC 2021] Imprecise Permutation Sort

这是一个交互题。 有一个由 $1$ 到 $n$ 的整数构成的排列 $a[1], a[2], \ldots, a[n]$ 被隐藏了起来。 你的任务是通过比较和交换元素对，将其按升序排序。本题本应很简单，但出题人因为在 G 和 J 题中过于专注于浮点数运算，实现了一个“不精确”的比较器： - 如果 $\frac{|a[i] - a[j]|}{\max(a[i], a[j])} \leq 0.01$，则返回 $0$； - 否则，如果 $a[i] < a[j]$，则返回 $-1$； - 否则，返回 $1$。 你的程序可以使用该比较器对任意两个元素进行比较，也可以交换任意两个元素。每次交换后，系统会告知当前排列是否已经有序。 请在不超过 $300\,000$ 次查询内，将长度不超过 $16\,384$ 的排列排序。 ### 交互说明 首先，你会收到一个整数 $n$，表示排列的长度（$1 \leq n \leq 16\,384$）。然后，你可以输出查询，并读取系统的响应。每次查询后需要刷新输出，并读取一个整数作为响应。 比较查询格式为 $\tt{C\ i\ j}$，交换查询格式为 $\tt{S\ i\ j}$，其中 $i$ 和 $j$ 是元素的下标（$1 \leq i, j \leq n$）。允许 $i = j$。 比较查询的响应为： - $0$，如果 $a[i]$ “近似等于” $a[j]$； - $-1$，如果 $a[i] < a[j]$； - $1$，如果 $a[i] > a[j]$。 交换查询会交换 $a[i]$ 和 $a[j]$ 的值，响应为： - $1$，如果交换后数组已按升序排列； - $0$，否则。 一旦收到交换查询的响应为 $1$，你的程序应立即退出。 你的程序至少要进行一次交换查询。例如，如果初始排列已经有序，可以查询 $\tt{S\ 1\ 1}$，收到 $1$ 后退出。 交互器是非自适应的。排列在你第一次查询前就已确定。

无。

无。

由 ChatGPT 4.1 翻译