Cod sursa(job #603687)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 18 iulie 2011 13:10:09
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include<stdio.h>

#define maxN 30005

FILE*f=fopen("order.in","r");
FILE*g=fopen("order.out","w");

int n,i,v,A[4*maxN],x,aux;

void init ( int nod , int st , int dr ){
	
	A[nod] = dr - st + 1;
	
	if ( st == dr ){
		return ;
	}
	
	int mij = (st + dr) >> 1;
	int nodst = nod << 1;
	int noddr = nodst + 1;
	
	init(nodst,st,mij);
	init(noddr,mij+1,dr);
}

void query ( int nod , int st , int dr ){
	
	if ( st == dr ){
		fprintf(g,"%d ",st); x = st;
		return ;
	}
	
	int mij = (st + dr) >> 1;
	int nodst = nod << 1;
	int noddr = nodst + 1;
	
	if ( A[nodst] >= v ){
		query(nodst,st,mij);
	}
	else{
		v -= A[nodst];
		query(noddr,mij+1,dr);
	}
}

void update ( int nod , int st , int dr ){
	
	if ( st == dr ){
		A[nod] = 0;
		return ;
	}
	
	int mij = (st + dr) >> 1;
	int nodst = nod << 1;
	int noddr = nodst + 1;
	
	if ( x <= mij ){
		update ( nodst, st, mij );
	}
	else{
		update ( noddr,mij+1,dr );
	}
	
	A[nod] = A[nodst] + A[noddr];
}

int main () {
	
	fscanf(f,"%d",&n);
	
	init(1,1,n);
	
	for ( aux = 1,i = 1 ; i <= n ; ++i ){
		if ( i == 1 ){
			aux = v = 2;
		}
		else{
			v = (aux + i - 2) % ( n - i + 1 ) + 1; aux = v;
		}
		query(1,1,n);
		update(1,1,n);
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}