记录编号	461715	评测结果	A
题目名称	[UVa 1402] 机器排序	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	0.304 s
提交时间	2017-10-20 14:54:51	内存使用	1.08 MiB

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
using namespace std;
inline int read(){
	int sum(0);
	char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum;
}
struct data{
	int pos,w;
}a[100005];
inline bool cmp1(const data &a,const data &b){return a.w==b.w?a.pos<b.pos:a.w<b.w;}
inline bool cmp2(const data &a,const data &b){return a.pos<b.pos;}
#define get_size(x) (x?x->size:0)
#define get_mn(x) (x?x->mn:0x7fffffff)
struct node{
	node *lch,*rch;
	int key,fix,mn,size,mark;
	node(int x=0):lch(NULL),rch(NULL),key(x),fix(rand()),mn(x),size(1),mark(0){}
	inline void revs(){swap(this->lch,this->rch);mark^=1;}
	inline void pushup(){
		this->size=get_size(this->lch)+get_size(this->rch)+1;
		this->mn=min(this->key,min(get_mn(this->lch),get_mn(this->rch)));
	}
	inline void pushdown(){
		if(this->mark){
			if(this->lch)this->lch->revs();
			if(this->rch)this->rch->revs();
			this->mark=0;
		}
	}
}*root;
typedef pair<node*,node*> pii;
inline node* merge(node *x,node *y){
	if(!x)return y;
	if(!y)return x;
	x->pushdown();y->pushdown();
	if(x->fix<y->fix){
		x->rch=merge(x->rch,y);
		x->pushup();
		return x;
	}
	else{
		y->lch=merge(x,y->lch);
		y->pushup();
		return y;
	}
}
inline pii split(node *x,int k){
	if(!x) return pii(NULL,NULL);
	x->pushdown();
	pii y;
	if(get_size(x->lch)>=k){
		y=split(x->lch,k);
		x->lch=y.second;
		x->pushup();
		y.second=x;
	}
	else{
		y=split(x->rch,k-get_size(x->lch)-1);
		x->rch=y.first;
		x->pushup();
		y.first=x;
	}
	return y;
}
inline int dfs(node *now,int x){
	if(!now)return 0;
	now->pushdown();
//	cout<<"dfs this->"<<now->key<<endl;
	if(now->key==x)return get_size(now->lch);
	if(get_mn(now->lch)==x)return dfs(now->lch,x);
	return get_size(now->lch)+1+dfs(now->rch,x);
}
inline void print(node *x){
	if(!x)return;
	x->pushdown();
	print(x->lch);
	printf("this->%d\n",x->key);
	print(x->rch);
}
int main(){
	freopen("roboticsort.in","r",stdin);
	freopen("roboticsort.out","w",stdout);
	while(1){
		int n(read());
		if(!n)break;
		for(int i=1;i<=n;++i)a[i].w=read(),a[i].pos=i;
		sort(a+1,a+n+1,cmp1);
		for(int i=1;i<=n;++i)a[i].w=i;
		sort(a+1,a+n+1,cmp2);
		root=new node(a[1].w);
		for(int i=2;i<=n;++i)root=merge(root,new node(a[i].w));
//		print(root);
		int ans(dfs(root,1)+1);
		printf("%d",ans);
//		cout<<"ans="<<ans<<endl;
		pii tp(split(root,ans));
		tp.first->revs();
		root=merge(tp.first,tp.second);
//		print(root);
		for(int i=2;i<=n;++i){
			pii tp1,tp2;
			tp1=split(root,i-1);
			int ans(dfs(tp1.second,i)+i);
			printf(" %d",ans);
			tp2=split(tp1.second,ans-i+1);
//			cout<<"ans="<<ans<<endl;
//			pii tp1(split(root,i-1)),tp2(split(tp1.second,ans-i+1));
			tp2.first->revs();
			tp1.second=merge(tp2.first,tp2.second);
			root=merge(tp1.first,tp1.second);
	//		cout<<"root->"<<root->key<<endl;
	//		print(root);
		}
		puts("");
	}
}