记录编号	186842	评测结果	AAAAAAAAAA
题目名称	1539.[Ural 1568] 火车车厢排序	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.086 s
提交时间	2015-09-15 17:24:38	内存使用	0.35 MiB

#include<cstdio>
#include<iostream>
#include<deque>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int N,P[10010]={0};
deque<int> ans[20];
void read()
{
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
		scanf("%d",&P[i]);
}
int now=0;
void make_ans()
{
	pair<int,int> date[10010];
	memset(date,0,sizeof(date));
	for(int i=1;i<=N;i++)
		date[i]=make_pair(P[i],i);
	sort(date+1,date+1+N);
	int rpos[10010]={0};
	rpos[1]=1;
	int rnum=1;
	for(int i=1;i<=N;i++)
	{
		if(date[i].second>date[i-1].second) rpos[date[i].first]=rnum;
		else rpos[date[i].first]=++rnum;
	}
	for(int i=1;i<=N;i++) if(rpos[P[i]]&1) ans[now].push_back(P[i]);
	for(int i=1;i<=N;i++) if(!(rpos[P[i]]&1)) ans[now].push_back(P[i]);
	for(int i=1;i<=N;i++) P[i]=ans[now][i-1];
}
void work()
{
	for(int i=1;i<=N;i++)
		ans[0].push_back(P[i]);
	while(true)
	{
		bool ok=1;
		for(int i=1;i<=N;i++)
		{
			if(P[i]!=P[i-1]+1){ok=0;break;}
		}
		if(ok==1) break;
		now++;
		make_ans();
	}
	printf("%d\n",now);
	for(int i=0;i<=now;i++)
	{
		for(int j=0;j<ans[i].size();j++)
			printf("%d ",ans[i][j]);
		printf("\n");
	}
}
int main()
{
	freopen("traincarsorting.in","r",stdin);
	freopen("traincarsorting.out","w",stdout);
	read();
	work();
	return 0;
}