这是一道交互题。

Old Pigeon是一名神仙OI选手，在鸽国信息学冬令营PWC2017 Challenge一题中仅用$1ms$就完成了第二个子任务——对于$2\times {10}^8$个数排序，吊打了$std$。当ljt12138向他询问解题方法时，他总是笑而不语。

进入鸽华大学后，他遇到了这样一道数据结构课习题：给你$n$个数和一个三元比较器$compare(x,y,z)$，你可以给三元比较器三个数，它会将最大的数和最小的数返回给你，要求你用尽可能少的次数给$n$个数排序。看到这道似曾相识的题目，Old Pigeon变得暴躁了起来：“我有一只神奇的排序鸽，你给它不超过$k$个数，它就能将$k$个数返回给你，比三元比较器高到不知哪里去了！”

在PWC2017中获得狗牌的ljt12138想知道，如果你有一只这样的排序鸽，可以在多少次比较之内将$n$个数排序呢？

任务介绍

你需要实现一个函数sort(int id, int n, int k, int *a)：

• $1\le id\le 3$为传入的子任务编号；
• $n$为序列长度；
• $k$为排序鸽允许的最大排序个数；
• $a$为传出答案的数组。

你需要将排序后第$1\le i\le n$小的数在原数列中的位置$0\le p<n$，存放到$a[i-1]$的位置。所有的下标都是从0开始的。

举例而言，如果待排序的数组$A=[3,2,0,1,4]$，排好序后的数组是$A^{\prime }=[0,1,2,3,4]$，你应当返回的数组$a=[2,3,1,0,4]$。

在每个测试点中，交互库都会调用恰好一次sort函数。

你可以调用函数super_sort(int *a, int len, int *b)来请求排序鸽为你排序：

• $len$表示待排序的数的个数，要求$len\le k$；
• $a$传入待排序的数在原数列中的位置，且$0\le a[i]<n$；
• $b$传出排好序的数在原数列中的位置，即$b$是$a$的一个排列，且对于任意的$i<j$，$A[b[i]]<A[b[j]]$。

实现方法

本题只支持C++。

源代码中需要包含头文件sort.h。

你需要实现的函数sort：

void sort(int id, int n, int k, int *a);

函数super_sort的接口信息如下：

void super_sort(int *a, int len, int *b);

如何测试你的程序

你需要在本题目录下使用如下命令编译得到可执行程序：

g++ grader.cpp sort.cpp -o sort -O2

可执行文件将从标准输入读取以下格式的数据：

• 第一行包含六个数：$id,n,k,L1,L2,L4$，其中$1\le id\le 3$为子任务编号，$n$为排序数组长度，$k$为排序鸽每次能排序的最长长度，$L1,L2,L4$为评分参数，将在子任务中解释用处。

• 第二行包含$n$个数：$A_0,A_1,\dots ,A_{n-1}$，表示待排序的数组。$A$应该是$\{0,1,2,\dots ,n-1\}$的一个排列，表示待排序的数组。

交互库将会输出以下信息：

• 如果数组成功排序，输出一行形如"cmp_cnt = cnt"，表示你调用super_sort的次数
• 否则，将输出对应的错误信息。

如果输入数据不合法，交互库可能不能正常运行。

你可以参考下发的交互库了解更多的信息。

交互式类型的题目怎么本地测试

样例源代码

按照上文中提到的方式进行编译，即能通过编译得到可执行程序。

样例源代码只是帮助理解题目，结果不一定正确。

由于提供了交互式验证答案正确性的方法，本题不提供输出样例。

样例一

input

0 8 2 100 1000 10000
2 1 0 3 4 6 5 7

注意： 样例中的$id=0$，在实际的测试数据中不会出现。这里仅用于演示输入的格式。

限制及约定

Subtask1（8分）：$n=1024,k=4,L1=5700,L2=10000,L4=100000$

Subtask2（24分）：$n=1024,k=16,L1=840,L2=1100,L4=3100$

Subtask3（68分）：$n=524288,k=16,L1=562000,L2=800000,L4=1016000$

对于每个子任务，设c = cmp_cnt：

• 如果 $c\le L1$ ，将获得子任务全部的分数；
• 如果 $L1<c\le L2$，将获得子任务一半的分数；
• 如果 $L2<c\le L4$ ，将获得子任务四分之一的分数；
• 如果 $L4<c$ 或没有成功排序，将不会获得任何分数，并被暴躁的排序鸽D一番。

时间限制：$\mathtt{\text{2s}}$

空间限制：$\mathtt{\text{512MB}}$

题目中所给的时间、空间限制为你的代码和交互库加起来可以使用的时间和空间。我们保证，对于任何合法的数据及在限制范围内的调用，任何版本的交互库（包括下发给选手的和最终评测使用的），运行所用的时间不会超过0.5s，运行所用的空间不会超过12MB，也就是说，选手实际可用的时间至少为1.5s，实际可用的空间至少为500MB。

下载

交互库下载