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

#include<cstdio>
#include<iostream>
#include<deque>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int N,P[10010]={0};
class miku
{
public:
	int x,id;
};
deque<miku> Q[3];
int tot=0;
void read()
{
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
		scanf("%d",&P[i]);
}
void make_Q()
{
	int W[10010]={0};
	deque<miku> tem[10010];
	int temp=0,temx=0;
	for(int i=1;i<=N;i++)
	{
		if(P[i]>P[i-1]) temx++;
		if(W[P[i]-1]==0) {tem[N-P[i]+1].push_back((miku){P[i],temx});tot++;W[P[i]]=N-P[i]+1;}
		else {tem[W[P[i]-1]].push_back((miku){P[i],temx});W[P[i]]=W[P[i]-1];}
	}
	for(int i=1;i<=N;i++)
	{
		if(tem[i].size()>0)
		{
			temp++;
			for(int j=0;j<tem[i].size();j++)
				Q[temp%2].push_back(tem[i][j]);
		}
	}
}
bool cmp(miku a,miku b)
{
	return a.id<b.id;
}
void make_P()
{
	sort(Q[0].begin(),Q[0].end(),cmp);
	sort(Q[1].begin(),Q[1].end(),cmp);
	int now=0;
	for(int i=0;i<Q[0].size();i++) P[++now]=Q[0][i].x;
	for(int i=0;i<Q[1].size();i++) P[++now]=Q[1][i].x;
}
void work()
{
	deque<int> ans[10010];
	int now=0;
	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++;
		for(int i=0;i<=1;i++) Q[i].clear();tot=0;
		make_Q();make_P();
		for(int i=1;i<=N;i++)
			ans[now].push_back(P[i]);
	}
	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;
}