UOJ Logo Universal Online Judge

UOJ

#445. 【集训队作业2018】暴躁的排序鸽

统计

这是一道交互题

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' = [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一番。

时间限制:$\texttt{2s}$

空间限制:$\texttt{512MB}$

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

下载

交互库下载