Cod sursa(job #744540)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 8 mai 2012 23:01:57
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include<fstream>
#define max 30007
using namespace std;


ifstream f("order.in");
ofstream g("order.out");
int arb[3*max],n,val,answer,nr,i;
void build (int nod,int st,int dr){
	
	if(st==dr){
		
		arb[nod]=1;
		return;
	}
	int m=(st+dr)/2;
	build(2*nod,st,m);
	build(2*nod+1,m+1,dr);
	arb[nod]=arb[2*nod]+arb[2*nod+1];
}
void query(int nod,int st,int dr,int val){
	
	if(st==dr){
		
		answer=st;
		return ;
	}
	int m=(st+dr)/2;
	if(arb[2*nod]>=val)
		query(2*nod,st,m,val);
	else
		query(2*nod+1,m+1,dr,val-arb[2*nod]);
}
void update(int nod,int st,int dr,int k){
	
	if(st==dr){
		arb[nod]=0;
		return ;
	}
	int m=(st+dr)/2;
	if(k<=m)
		update(2*nod,st,m,k);
	else
		update(2*nod+1,m+1,dr,k);
	
	arb[nod]=arb[2*nod]+arb[2*nod+1];
}
int main () {
	
	
	f>>n;
	
	
	build(1,1,n);
	val=2;
	nr=n;
	for(i=0;i<n;i++){
		
		val=(val+i-1)%(nr-i)+1;
		query(1,1,n,val);
		
		g<<answer<<" ";
		update(1,1,n,answer);
	}

	return 0;
}