记录编号	432782	评测结果	A
题目名称	[UVa 1402] 机器排序	最终得分	100
用户昵称	하루Kiev	是否通过	通过
代码语言	C++	运行时间	0.484 s
提交时间	2017-08-03 19:43:51	内存使用	1.46 MiB

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<ctime>
#include<cstring>
#define maxn 100050
using namespace std;
struct treap{
	   treap *ch[2];
	   int rd,size,v,flip,minn;
	   treap(int x){v=minn=x;ch[0]=ch[1]=NULL;size=1;rd=rand();flip=0;}
}*root;
#define size(x) ((x)?x->size:0)
typedef pair<treap*,treap*> tree;
void pushdown(treap *k){
	 if(k==NULL) return;
     if(k->flip%2){
        if(k->ch[0]){k->ch[0]->flip++;swap(k->ch[0]->ch[0],k->ch[0]->ch[1]);}
        if(k->ch[1]){k->ch[1]->flip++;swap(k->ch[1]->ch[0],k->ch[1]->ch[1]);}
     }k->flip=0;
}
void mitr(treap *k){
	 int t,a,b=0x7fffffff,c=0x7fffffff;
	 k->size=1+size(k->ch[0])+size(k->ch[1]);
	 a=k->v;
	 if(k->ch[0]) b=k->ch[0]->minn;
	 if(k->ch[1]) c=k->ch[1]->minn;
	 t=min(a,min(b,c));
	 if(t==a) k->minn=k->v;
	 if(t==b) k->minn=k->ch[0]->minn;
	 if(t==c) k->minn=k->ch[1]->minn;
}
treap *merge(treap *a,treap *b){
	  if(a==NULL) {mitr(b);return b;} 
	  if(b==NULL) {mitr(a);return a;}
	  pushdown(a);pushdown(b);
	  if(a->rd < b->rd){
	  	 a->ch[1]=merge(a->ch[1],b);
	  	 mitr(a);
	  	 return a;
	  }
	  else{
	  	 b->ch[0]=merge(a,b->ch[0]);
	  	 mitr(b);
	  	 return b;
	  }
}
tree split(treap *k,int x){
	 if(k==NULL) return tree(NULL,NULL);
	 tree y;
	 pushdown(k);
	 if(x<=size(k->ch[0])){
	 	y=split(k->ch[0],x);
	 	k->ch[0]=y.second;
	 	mitr(k);
	 	y.second=k;
	 }
	 else{
	 	y=split(k->ch[1],x-size(k->ch[0])-1);
	 	k->ch[1]=y.first;
	 	mitr(k);
	 	y.first=k;
	 }
	 return y;
}
struct node{int v,id;}a[maxn];
int cmp(node a,node b){if(a.v<b.v||(a.v==b.v&&a.id< b.id)) return true;return false;}
int Hash[maxn],n;
int main(){
    freopen("roboticsort.in","r",stdin);
    freopen("roboticsort.out","w",stdout);
	while(scanf("%d",&n)==1&&n){
		  root=NULL;
		  for(int i=1;i<=n;i++) scanf("%d",&a[i].v),a[i].id=i;
		  sort(a+1,a+1+n,cmp);
		  for(int i=1;i<=n;i++) Hash[a[i].id]=i;
		  for(int i=1;i<=n;i++){
		  	  treap *tr=NULL;
		  	  tr=new treap(Hash[i]);
		      root=merge(root,tr);
		  }
		  for(int i=1;i<=n;i++){
		  	  treap *tr=NULL;
		  	  tree x=split(root,i-1);
		  	  tr=x.second;
		  	  int pos=i;
		  	  while(tr->v!=tr->minn){
		  	  	   pushdown(tr);
		  	  	   if(tr->ch[0]&&tr->ch[0]->minn==tr->minn) tr=tr->ch[0];
		  	  	   else{
					   pos+=size(tr->ch[0])+1;
		  	  	       tr=tr->ch[1];
		  	  	   }
			  }
			  pos+=size(tr->ch[0]);
			  if(i!=n) printf("%d ",pos);
			  else printf("%d\n",pos);
			  tree y=split(x.second,pos-i+1);
			  y.first->flip++;
			  swap(y.first->ch[0],y.first->ch[1]);
			  mitr(y.first);
			  root=merge(x.first,merge(y.first,y.second));
		  }
	}
    return 0;
}