Cod sursa(job #143528)

Utilizator marius135Dumitran Adrian Marius marius135 Data 26 februarie 2008 17:11:45
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include<stdio.h>
long n,arb[(1<<17)];

void fa(long poz,long st,long dr)
{
	arb[poz] = dr - st +1;
	if( dr == st) return ;
	fa(poz*2,st,(st+dr)/2);
	fa(poz*2+1,(st+dr)/2+1,dr);
}
long afla( long poz, long st,long dr, long cat)
{
	if( dr <= cat)
		return arb[poz];
	if( st > cat) return 0;
	if( arb[poz] == 0) return 0;
	return afla(poz*2,st,(st+dr)/2,cat);
	return afla(poz*2+1,(st+dr)/2+1,dr,cat);
}
long afla2( long poz,long st,long dr,long cine)
{
	if( st == dr)
		return st;
	if( arb[poz*2] >= cine)
	{
		long x = afla2(poz*2,st,(st+dr)/2,cine);
		return x;
	}
	long x =  afla2(poz*2+1,(st+dr)/2+1,dr,cine-arb[poz*2]);
	return x;
}
void elimina(long poz,long st,long dr,long cine)
{
	if( cine < st || cine > dr)
		return ;
	arb[poz]--;
	if( st == dr) return;
	elimina(poz*2,st,(st+dr)/2,cine);
	elimina(poz*2+1,(st+dr)/2+1,dr,cine);
}
int main()
{
	freopen("order.in","r",stdin);
	freopen("order.out","w",stdout);
	
	scanf("%ld",&n);
	
	fa(1,1,n);
	
	long act = 1;
	for( long i = 1; i <= n; ++i)
	{
		long ask = afla(1,1,n,act) + i;
		ask %= (n-i+1);
		if( ask == 0) ask = n-i+1;
		act = afla2(1,1,n,ask);
		if( i == n)
			printf("%ld\n",act);
		else printf("%ld ",act);
		
		elimina(1,1,n,act);
	}

	
	
	
	return 0;
}