Cod sursa(job #541238)

Utilizator klamathixMihai Calancea klamathix Data 24 februarie 2011 22:06:15
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include<cstdio>

using namespace std;

const int maxn = 30005;

int i , j , n , k , Arb[4 * maxn] , aux , poz;

void build_tree(int node , int left , int right)
{
	if ( left == right ) {
		Arb[node] = 1;
		return;
	}
	
	int mid = (left + right) >> 1;
	build_tree(2 * node , left , mid );
	build_tree(2 * node + 1 , mid + 1 , right);
	
	Arb[node] = Arb[2 * node] + Arb[2 * node + 1];
}
	
void update (int node , int left , int right ) {
	
	if ( left == right ) {
		Arb[node]--;
		return;
	}
	
	int mid = (left + right) >> 1;
	if ( poz <= mid ) 
		update(2 * node , left , mid );
	else
		update(2 * node + 1 , mid + 1 , right);
	
	Arb[node] = Arb[2 * node] + Arb[2 * node + 1];
}

int query( int node , int left , int right ) {
	
	if ( left == right ) return left;
	
	int mid = ( left + right ) >> 1;
	
	if ( Arb[2 * node] >= aux )
		return query( 2 * node , left , mid );
	else {
		aux -= Arb[2 * node];
		return query( 2 * node + 1 , mid + 1, right);
	}
}

int main()
{
	freopen("order.in","r",stdin);
	freopen("order.out","w",stdout);
	
	scanf("%d",&n);
	
	build_tree(1 , 1 , n);
	
	int t = 1;
	
	for( i = 1 ; i <= n ; ++i ) {
		t = (t + i) % Arb[1];
		if (!t) t = Arb[1];
		aux = t;
		int x = query (1 , 1 , n);
		printf("%d ",x);
		poz = x;
		update(1 , 1 , n);
		--t;
		if(!t) t = Arb[1];
	}
	
return 0;
}