Cod sursa(job #548663)

Utilizator SadmannCornigeanu Calin Sadmann Data 7 martie 2011 18:01:03
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 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;
}