Cod sursa(job #381263)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 9 ianuarie 2010 19:21:32
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <stdio.h>

int a[65001],b[65001];

inline int place(int l,int r,int nod,int i)
{
	--a[nod];
	if (l==r) return l;
	if (i<=a[2*nod]) return place(l,(l+r)/2,2*nod,i);
	else return place((l+r)/2+1,r,2*nod+1,i-a[2*nod]);
}

inline int query(int nod,int s,int d,int l,int r)
{
	if ((d<l)||(s>r)) return 0;
	if ((l<=s)&&(d<=r)) return a[nod];
	return query(2*nod,s,(s+d)/2,l,r)+query(2*nod+1,(s+d)/2+1,d,l,r);
}

int main()
{
	int n,i,y,x=2,z;
	freopen("order.in","r",stdin);
	freopen("order.out","w",stdout);
	scanf("%d",&n);
	do
	{
		x*=2;
	}
	while (x<n);
	b[0]=1;
	for (i=x;i<x+n;i++) a[i]=1;
	for (i=x-1;i>0;i--) a[i]=a[2*i]+a[2*i+1];
	for (i=1;i<n+1;i++)
	{
		y=query(1,1,x,1,b[i-1]);
		if ((i+y)%a[1]==0) z=a[1];
		else z=(i+y)%a[1];
		b[i]=place(1,x,1,z);
	}
	for (i=1;i<n+1;i++) printf("%d\n",b[i]);
	return 0;
}