1302: Optimal sort
题目
题目描述
有一个 $1 \dots n$ 的排列，你需要对他进行排序。你无法直接获得他们的大小，仅能通过比较来得到大小关系。
由于比较排序的复杂度有 $\Omega(n \log n)$ 的下界，为了使得你的程序非常优秀，你只能进行至多 $$ n \left\lceil \log_2 (n) \right\rceil - (n - 1) $$ 次询问。
How do we judge your answer
本题是交互题。你仅需要实现 void optimal_sort(int n) 函数，表示对一个长度为 $n$ 的排列 ${p_1, \dots, p_n}$ 进行排序。
你的代码前需要声明函数原型 int query(int, int);。
在 optimal_sort 中，
- 可以调用
int query(int x, int y)表示比较标号为 $x, y$ 的大小。返回值为 ${-1, 0, 1}$ 中的一个数，表示 $p_x < p_y, p_x = p_y$ 以及 $p_x > p_y$。 - 确信答案正确后，请往 stdout 中输出一行由 $n$ 个空格隔开的整数，表示排名为 $i$ 的数在 $p$ 中的位置下标是多少，并退出函数。
如果你的函数进行了第 $n \left\lceil \log_2 (n) \right\rceil - n + 2$ 次询问，你会得到 Wrong Answer ，并在 info 里可以看到 operation limit exceeded。
如果你的输出错误，你会得到 Wrong Answer。
如果你进行了非法的操作，你可能得到 Wrong Answer ，并在 info 里看到 invalid query。
Constraints
本题有 $10$ 组测试数据，每组 $10$ 分，$n$ 取值分别为 $2, 4, 8, \dots, 1024=2^{10}$。 评测器使用的排列不会因为你的回答而改变。
对于每组测试，我们会调用你的程序至多 $100$ 次，请记得在每次调用时清空所用到的全局变量。
Time Limit: 3s for 100 cases
Memory Limit: 128MB
Sample Interaction
txt
n = 2, hidden array = [2, 1]
call optimal_sort(2):
query(1, 2), returned 1
exit optimal_sort
n = 2, hidden array = [1, 2]
call optimal_sort(2):
query(1, 2), returned -1
exit optimal_sort
期望输出：
txt
2 1
1 2
Note
你可以使用以下程序来测试你的代码，方法是将你的代码将这段代码粘贴到你的代码最后。这段代码不会对你的行为进行任何检查。
请注意，提交的代码里不应该有 main 函数。
```cpp
include
int __qcnt = 0; int __hidden_array[1024]; int query (int x, int y) { __qcnt ++; int d = __hidden_array[x] - __hidden_array[y]; return d > 0 ? 1 : (d == 0 ? 0 : -1); } int main() { int n; std::cin >> n; for (int i = 1; i <= n; i++) std::cin >> __hidden_array[i]; optimal_sort(n); std::cout << "number of queries : " << __qcnt << std::endl; } ```
以下代码是针对 $n = 2$ 的参考代码实现，你可以从中了解提交的格式。
```cpp
include
using namespace std; int a[1024 + 1]; int query(int x, int y); void solve(int l, int r) { if (l >= r) return; if (r - l > 1) { cout << "Sorry, " << r - l + 1 << " is too difficult for me!" << std::endl; return; } if (query(a[l], a[r]) == 1) { swap(a[l], a[r]); } } void optimal_sort(int n) { for (int i = 1; i <= n; i++) a[i] = i; solve(1, n); for (int i = 1; i <= n; i++) printf("%d%c", a[i], i == n ? '\n' : ' '); } ```
Oops! 本题目还没有解答！
助教老师们编题的速度，已经超过了解题的速度！
OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。
如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！