Cod sursa(job #143852)

Utilizator raduzerRadu Zernoveanu raduzer Data 26 februarie 2008 21:55:09
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <stdio.h>

int n,i,j,d[70000],p,vp,poz,t,x,y,s,q,z;

void calc(int p, int a, int b)
{
	int v=(a+b)/2;
	if (a>=x && v<=y) s+=d[p*2];
	else if (x>=a && x<=v) calc(p*2,a ,v);
	if (v+1>=x && b<=y) s+=d[p*2+1];
	else if (y<=b && y>=v+1) calc(p*2+1, v+1, b);
}

void search(int p, int a, int b)
{
	int v=(a+b)/2;
	if (a==b)
	{
		printf("%d ",p-vp+1);
		poz=p-vp+1;
		d[p]=0;
		q=1;
		return;
	}
	if (d[p*2]<t && a>=poz) t-=d[p*2];
	else if (d[p*2]>=t && poz<=v) if (q==0) search(p*2,a,v);
	if (q==0) search(p*2+1,v+1,b);
	d[p]=d[p*2]+d[p*2+1];
}

int main()
{
	freopen("order.in","r",stdin);
	freopen("order.out","w",stdout);
	scanf("%d",&n);
	vp=0;
	while (vp<n) vp=1<<(++p);
	for (i=vp; i<vp+n; ++i) d[i]=1;
	for (i=p-1; i>=0; --i)
		for (int j=1<<i; j<1<<(i+1); ++j) d[j]=d[j*2]+d[j*2+1];
	poz=2;
	for (i=1; i<=n; ++i)
	{
		t=i;
		x=poz;
		y=vp;
		s=0;
		q=0;
		calc(1,1,vp);
		if (s<t)
		{
			t-=s;
			t%=d[1];
			if (t==0) 
			{
				t=d[1];
			}
			poz=1;
		}
		search(1,1,vp);
	}
	return 0;
}