题目描述

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

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

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

评分方法请见【数据范围与提示】一节。

数据范围与提示

本题共 $1$ 个测试点，$n=10^5$。在这个测试点中，你的 \text{my_sort} 函数会被调用恰好 $10$ 次。每次球的大小均匀独立随机生成且两两不同。

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

• 否则设你一共调用了 $p$ 次 $\text{query}$，若 $p>10^8$ 你会得到 $0$ 分，否则设 $q=10\lceil \log_2(n!)\rceil=15167050$，你的得分为 $\lfloor \sum_{i=1}^{100}(\frac{q}{p})^i+0.5 \rfloor$。

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

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

#include "sort.hpp"
#include <bits/stdc++.h>
std::vector<int> my_sort(int n)
{
	std::vector<int> v;
	for(int i=0;i<n;++i) v.push_back(i);
	sort(v.begin(),v.end(),query); return v;
}