1248: 最优排序

题目描述

请注意，本题为非传统题，你不应该期望在此题得到满分，根据你做法的优劣你将得到不超过 100 的一个分值。本题只支持 C++ 语言，不保证使用其他语言能通过编译。

有 $n$ 个编号分别为 $0, 1, \cdots n - 1$ 的球。这 $n$ 个球的大小两两不同。你每次可以比较两个球的大小关系，你需要调用尽量少次比较将它们排序。

你需要在程序的第一行 #include "sort.hpp"。你不应该实现 main 函数，你只需要实现一个函数： c++ std::vector<int> my_sort(int n) 它接受球的个数，返回球按大小从小到大排列后的编号顺序。你可以调用一个函数： c++ bool query(int a, int b) 如果球 $a$ 比球 $b$ 轻，该函数会返回 $1$，否则返回 $0$ 。

输入格式

输出格式

样例输入

样例输出

数据范围

本题共 1 个测试点，$n = 10^3$。

在这个测试点中，你的 my_sort 函数会被调用恰好 $10$ 次。每次球的大小均匀独立随机生成且两两不同。

若你没有正确地将球按大小排序，你得到 $0$ 分。

否则设你一共调用了 $p$ 次 query，若 $p > 10^8$ 你会得到 $0$ 分，否则设 $q = 10\lceil \log_2 (n!)\rceil = 85300$，你的得分为 $$\lceil 10\sum_{i=0}^{10} (\frac{q}{p})^i\rceil$$

请不要恶意攻击交互库（包括但不限于查看交互库源码并生成相同的排列、读取内存）。

一个可以获得分数的程序：

```c++

include "sort.hpp"

std::vector my_sort(int n) { std::vector v; for(int i=0;i<n;++i) v.push_back(i); for (int i = 0; i < n; i++) for (int j = i - 1; j >= 0; j--) if (query(v[j + 1], v[j])) { int t = v[j]; v[j] = v[j + 1]; v[j + 1] = t; } return v; } ```

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！