UOJ Logo

NOI.AC

#32. Sort

统计

排序

题目描述

众所周知,排序方法有许多种。例如:简单易懂的冒泡排序,平均复杂度较优的快速排序,以及不基于比较的基数排序等等。

现在,小 $D$ 得到了一个自然数序列 $\{a_1,a_2,\cdots,a_n\}$。他想要对其按照从小到大的顺序进行排序(即使得每个元素均严格不大于他的后继元素)。但由于基于比较的排序算法复杂度下界已经被证明为 $\Theta (n\log_2n)$,所以小 $D$ 决定尝试一种全新的排序算法:翻转排序

在翻转排序中,小 $D$ 在每次操作中,可以选择一个区间 $[l,r]$ $(1\le l\le r\le n)$,并翻转 $a_l,a_{l+1},\cdots,a_r$。即,在该次操作完后,序列将会变为 $a_1,a_2,\cdots,a_{l-1},a_r,a_{r-1},\cdots,a_{l+1},a_l,a_{r+1},a_{r+2},\cdots,a_n$。

例如,对于序列 $[1,6,2,4,3,5]$,若选择区间 $[2,4]$ 进行翻转,则将会得到 $[1,4,2,6,3,5]$。

定义一次操作的代价为 $r-l+1$,即翻转的区间长度。定义一个操作序列的代价为每次操作的代价之和。现在,请你帮助小 $D$ 求出一个代价足够小的操作序列(你并不一定要求出代价最小的操作序列)。

输入格式

第一行一个正整数 $n$,表示序列长度。

第二行 $n$ 个空格隔开的非负整数,表示小 $D$ 得到的自然数序列 $a_1,a_2,\cdots,a_n$。

输出格式

输出若干行,每行两个空格隔开的正整数 $l,r$ $(1\le l\le r\le n)$,表示一次翻转区间 $[l,r]$ 的操作。

最后输出一行 -1 -1,标志着操作序列的结束。

样例输入

4
1 3 2 4

样例输出

2 3
-1 -1

样例解释

在一次操作 $[2,3]$ 后,序列变为 $[1,3,2,4]$,满足从小到大排列的要求。因此这是一种合法的输出,且代价为 $3-2+1=2$。

因为你可以自行生成数据并判断你的输出是否正确(见 “评分方式” 一节),故本题不再提供更多的样例数据。

评分方式

对于每个测试点,若你的输出格式符合题目要求,且输出的操作序列可以将输入的序列按照从小到大的顺序排序,并且该操作序列的代价不超过 $2\times 10^7$,则该测试点得满分,否则不得分。

下发文件中提供了 checker.cpp,该程序将对于其所在目录下的 sort.in,判断其所在目录下的 sort.out 是否为一个正确的操作序列。若正确,将给出该操作序列的代价。若不正确,将给出错误信息。选手可以借助该程序来更好地检查自己的程序是否正确。

运行时,必须保证 sort.in 为一个合法的输入,且需保证 sort.out 符合题目中描述的输出格式,否则出现任何结果均有可能。

数据规模与约定

本题共 $20$ 个测试数据,每个测试数据 $5$ 分。

对于所有测试数据,保证 $1\le n\le 50000$,且 $0\le a_i\le 10^9$。以下为每个测试数据的数据范围及性质:

测试数据编号 $n\le$ 特殊性质 $\ast$ 测试数据编号 $n\le$ 特殊性质 $\ast$
$1$ $5$ $\surd$ $11$ $5000$ $\times$
$2$ $5$ $\times$ $12$ $5000$ $\times$
$3$ $7$ $\surd$ $13$ $10000$ $\surd$
$4$ $7$ $\times$ $14$ $20000$ $\surd$
$5$ $10$ $\surd$ $15$ $30000$ $\surd$
$6$ $10$ $\times$ $16$ $40000$ $\surd$
$7$ $3000$ $\times$ $17$ $50000$ $\surd$
$8$ $4000$ $\surd$ $18$ $30000$ $\times$
$9$ $4000$ $\times$ $19$ $40000$ $\times$
$10$ $5000$ $\surd$ $20$ $50000$ $\times$

其中,若 “特殊性质 $\ast$” 一栏为 “$\surd$”,则保证该测试数据中:输入的序列 $a_1,a_2,\cdots,a_n$ 仅由 $0$ 或 $1$ 组成。否则不保证这一点成立。

友情提示:本题输出数据量可能较大,对于 C++ 选手,请不要使用 (std::)endl 进行换行。一种替代方法为 "\n",例如使用 std::cout << x << "\n"; 而非 std::cout << x << std::endl;,否则可能导致超时。

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

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

checker.cpp

checker.cpp