Cod sursa(job #249504)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 28 ianuarie 2009 17:07:55
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <stdio.h>
int n,i,nr,poz,AI[60005];

void update(int nod,int l,int r,int x,int ok){
	if (l==r){ AI[nod]=ok; return;}
	int m=(l+r)>>1;
	if (x<=m) update ( nod<<1, l, m, x, ok );
	else update ((nod<<1)|1, m+1, r, x, ok );
//update AI[nod]
	AI[nod]=AI[nod<<1]+AI[(nod<<1)|1];
}
void query(int nod,int l,int r,int x){
	if (l>0&&r<=x){ nr+=AI[nod]; return;}
	int m=(l+r)>>1;
	if (m)query(nod<<1,l,m,x);
	if (m<x)query((nod<<1)|1,m+1,r,x);
}
void search(int nod,int l,int r,int nr){
	if (l==r){poz=l;return;}
	int m=(l+r)>>1;
	if (nr<=AI[nod<<1]) search(nod<<1,l,m,nr);
	else search((nod<<1)|1,m+1,r,nr-AI[nod<<1]);
}
int main(){
  freopen("order.in","r",stdin);freopen("order.out","w",stdout);
	scanf("%ld",&n);
	for (i=1;i<=n;++i)update(1,1,n,i,1);
	for (i=1,poz=1;i<=n;++i){
	  nr=i; query(1,1,n,poz);
		nr%=AI[1];if (!nr)nr=AI[1];
		search(1,1,n,nr);
		printf("%ld\n",poz);
		update(1,1,n,poz,0);
	}
return 0;
}