Skip to content

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 中,

  1. 可以调用 int query(int x, int y) 表示比较标号为 $x, y$ 的大小。返回值为 ${-1, 0, 1}$ 中的一个数,表示 $p_x < p_y, p_x = p_y$ 以及 $p_x > p_y$。
  2. 确信答案正确后,请往 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了,可以的话,请您参考添加页面,与大家一起分享你的题解!