[CERC2007]机器排序

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file roboticsort.in Output file roboticsort.out

【题目描述】

在布拉格捷克理工大学(Czech Technical University)某个幽深的角落,有一些实验室用来检测各种材料的机械和电气性能。在昨天的一项展示中,你已经见识了其中的一间是如何变成全新的多媒体实验室的。但那里仍然有别的实验室,服务于它们最初的用途。

在这个任务中,你将要给这样的一间实验室中一个搬运样品的机器人编写程序。设想有一些材料样品在一条传送带上排成一排。这些样品有不同的高度,这可能会给接下来的处理带来麻烦。为了消除这样的隐患,我们需要将这些样品按高度升序排列。

排序由一条机械臂完成,它可以抱起一些连续的样品并且将它们掉头,这样一来它们在传送带上的顺序就被翻转。换句话说,一个操作可以翻转A到B(含两端)的样品顺序。

给样品排序的一个可能方式是找到高度最小的样品P1,将1到P1的样品顺序翻转。这将使得P1成为第一个样品。接下来我们找到高度第二小的样品P2,将2到P2的样品顺序翻转。然后找到高度第三小的样品,以此类推。

这张图片展示了一个含6个样品的简单例子。高度最小的样品在4号位置,因此机械臂旋转前4个样品。高度第二小的样品在6号位置,因此下一个操作是翻转2-6号样品位置。第三步是翻转3-4号样品位置,以此类推。

你的任务是找到用上述算法给样品排序时正确的翻转操作序列。如果不止一个样品有相同的高度,必须保持它们的顺序不变:在初始序列中靠前的在最终序列中也应该靠前。

【输入格式】

输入包含多组数据。

每组数据有两行。第一行是一个正整数N,即样品个数(1<=N<=100000)。

第二行有N个由空格分隔的正整数,即各样品的高度,按最初的样品顺序给出。

输入结束标志为一行一个0。

【输出格式】

对每组数据,输出一行恰好N个整数P1,P2,...,PN,彼此由空格分隔。每个Pi应该是一个正整数(1<=Pi<=N),给出了第i次翻转操作前第i个样品的位置。

注意如果一个样品已经站在了正确的位置Pi上,你也应该输出Pi,表明“Pi到Pi的样品”(即Pi一个样品)应该被翻转。

【样例输入】

6
3 4 5 1 6 2
4
3 3 2 1
0

【样例输出】

4 6 4 5 6 6
4 2 4 4 

【来源】

Central Europe Regional Contest 2007 Robotic Sort

UVa 1402 Robotic Sort