题目类型说明

这是一道提交函数题 / 交互式思维题。你需要实现函数 multisort，通过调用评测器提供的 compare 接口完成排序；不要编写 main 函数。

题目描述

Humpty-Dumpty sat on a wall,
Card after card fell to the ground.
All the king’s horses and all the king’s men
can’t sort them back into place again!

正如这首小诗所说，Humpty-Dumpty 把他的一叠牌掉到了地上。这副牌共有 N 张，现在谁也不知道它们原本的正确顺序。于是他向 Alice 求助。

Alice 听说过一些基于成对比较的快速排序方法，但她觉得那样不够高效。不过，她有一种特殊能力：她一次最多可以抓起 K 张牌，并立刻知道这 K 张牌的正确相对顺序。她想知道，是否存在一种排序方法能够利用这种能力。她的目标是：用尽可能少的这类“K 元比较”将整副牌排好序。

经过长时间思考，Alice 还是没想到好办法，于是来向你求助。请编写程序 multisort.cpp，与 Alice（也就是评测器程序）通信，在尽量少的比较次数下完成排序。

实现细节

你需要实现如下函数：

std::vector<int> multisort(int n, int k);

该函数只会被调用一次，参数分别表示要排序的牌数，以及 Alice 一次最多能比较的牌数。函数需要返回一个向量，它是 0 到 N-1 的一个排列，表示这些牌应按什么顺序排列才能使其值从小到大有序。这里牌是用它们在初始打乱状态下的位置（索引）来表示的。

评测器还提供如下函数：

void compare(std::vector<int>& elems);

你的程序可以任意多次调用它。传入的参数是一个向量，表示要交给 Alice 比较的牌的下标。这个向量长度至多为 K，其中允许出现重复下标。函数执行后会把这个向量原地排序，使其中所表示的牌按实际大小从小到大排列。该操作的复杂度是 O(M \log \log M)，其中 M 是传入向量的长度。

你的程序必须实现 multisort，但不能包含 main() 函数，也不能从标准输入读取或向标准输出打印内容。程序开头必须包含：

#include "multisort.h"

只要满足上述条件，你的程序可以包含任意辅助函数、变量、常量等。

约束

• 所有测试中都固定有 N = 20000
• 2 ≤ K ≤ 1000

评分方式

每个测试点单独计分。对于某个测试点，只要你的 multisort 成功结束并返回一个长度为 N 的正确排列，该测试点就会得到非零分。

你在该测试点得到的分数为：

$$\text{该测试点满分} \times \min\left(1,\left(\frac{\text{authorScore}+1}{\text{yourScore}+1}\right)^{0.75}\right)$$

其中：

• yourScore：你的程序在该测试点中调用 compare 的次数；
• authorScore：作者程序在 30 个具有相同 N 和 K、但排列不同的测试中运行后，取其中最差的 10 次结果里的最大值。

原题进一步说明：对给定的 N 和 K，作者程序的期望比较次数与理论最优值（从单次比较所提供的信息量角度得到）同阶；更具体地说，当 K 不太小时，作者程序的比较次数大约是理论最优值的两倍。

测试分布

测试比例	K 的范围
10%	2 ≤ K < 5
	5 ≤ K < 10
	10 ≤ K < 20
30%	20 ≤ K < 100
40%	100 ≤ K ≤ 1000

每个测试中的牌排列都是随机生成的，即所有排列等概率出现。

样例交互

步骤	multisort 的动作	评测器的动作与返回
1		multisort(4, 3)
2	compare({0, 1, 2})	elems = {1, 0, 2}
3	compare({1, 2, 3})	elems = {1, 3, 2}
4	compare({0, 3})	elems = {3, 0}
5	return {1, 3, 0, 2}

说明

这里为了演示，取 N = 4 且 K = 3。
四张牌的实际值分别为：

• v_0 = 2
• v_1 = 0
• v_2 = 3
• v_3 = 1

第一次比较得到：v_1 < v_0 < v_2。
第二次比较得到：v_1 < v_3 < v_2。
第三次比较得到：v_3 < v_0。

因此唯一可能的整体顺序是：

v_1 < v_3 < v_0 < v_2

该程序总共使用了 3 次比较。

本地测试

题目提供了 multisort.h 和 Lgrader.cpp，你可以把它们与你的程序一起编译进行本地测试。

运行程序时，需要输入 K 以及用于生成排列的随机种子（seed）。如果你想用别的方式配置本地测试器，也可以自由修改题目提供的文件。

题目保证：评测系统中的 grader 行为与提供的本地 grader 一致。最重要的是，compare 函数的实现完全相同。