Cod sursa(job #569949)

Utilizator avram_florinavram florin constantin avram_florin Data 2 aprilie 2011 12:55:19
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include<fstream>

using namespace std;

const int MaxArb = 1 << 17;
int N,who,nr,poz,val;
int Arb[MaxArb];

ifstream f ("order.in");
ofstream g ("order.out");

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

void query(int nod,int left,int right,int care)
{
	if( left == right )
		{
			g << left << ' ';
			who = left;
			return ;
		}
	int midd = (left + right )>>1;
	if( care <= nr + Arb[2*nod] )
		query(2*nod,left,midd,care);
		else
		{
			nr += Arb[2*nod];
			query(2*nod+1,midd+1,right,care);
		}
}

int main()
{
	f >> N;
	for( int i = 1 ; i <= N ; i++ )
		{
			poz = i;
			val = 1;
			update(1,1,N);
		}
	int care = 2;
	for( int i = 1 ; i <= N ; i++ )
		{
			nr = 0;
			query(1,1,N,care);
			poz = who;
			val = -1;
			update(1,1,N);
			if( Arb[i] >= 1 )
				care = (care+i)%Arb[1];
			if( !care )
				care = Arb[1];
		}
	return 0;
}