Cod sursa(job #570007)

Utilizator avram_florinavram florin constantin avram_florin Data 2 aprilie 2011 13:28:11
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include<cstdio>

using namespace std;

const int MaxN = 30002;

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

void update(int nod,int left,int right,int poz,int val)
{
	if( left == right )
		{
			Arb[nod] += val;
			return;
		}
	int midd = left + (right-left)/2;
	if( poz <= midd )
		update(2*nod,left,midd,poz,val);
		else
		update(2*nod+1,midd+1,right,poz,val);
	Arb[nod] = Arb[2*nod]+Arb[2*nod+1];
}

void query(int nod,int left,int right ,int care)
{
	if(left == right )
		{
			printf("%d " , left );
			cine = left;
			return ;
		}
	int midd = left + (right-left)/2;
	if( nr + Arb[2*nod] >= care )
		query(2*nod,left,midd,care);
		else
		{
			nr += Arb[2*nod];
			query(2*nod+1,midd+1,right,care);
		}
}

int main()
{
	freopen( "order.in" , "r" , stdin );
	freopen( "order.out" , "w" , stdout );
	scanf("%d" , &N );
	int i,care;
	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];
		}
	return 0;
}