Cod sursa(job #500616)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 12 noiembrie 2010 16:54:30
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <stdio.h>
#define Nmax 30002

int Arb[Nmax*4];
int N,cine,nr;

void Update(int nod,int l,int r,int poz,int val){
	if( l==r ){
		Arb[nod]+=val;
		return;
	}
	int m=l+(r-l)/2;
	if( poz<=m ) Update(nod<<1,l,m,poz,val);
	else Update((nod<<1)+1,m+1,r,poz,val);
	Arb[nod]=Arb[nod<<1]+Arb[(nod<<1)+1];
}

void Query(int nod,int l,int r,int care){
	if( l == r ){
		printf("%d ",l);
		cine=l;
		return;
	}
	int m=l+(r-l)/2;
	if( nr+Arb[nod<<1] >= care ) Query(nod<<1,l,m,care);
	else{
		nr+=Arb[nod<<1];
		Query((nod<<1)+1,m+1,r,care);
	}
}

int main(){
	int i,care;
	freopen("order.in","r",stdin);
	freopen("order.out","w",stdout);
	scanf("%d",&N);
	for(i=1;i<=N;++i) Update(1,1,N,i,1);
	
	care=2;
	for(i=1;i<=N;++i){
		nr=0;
		Query(1,1,N,care);
		Update(1,1,N,cine,-1);
		if(Arb[1]>=1) care=(care+i)%Arb[1];
		if(!care) care=Arb[1];
	}
	
	fclose(stdin); fclose(stdout);
	return 0;
}