Cod sursa(job #270)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 8 decembrie 2006 12:08:08
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <stdio.h>

#define maxn 65536

int n,l,x,c,st;
int a[maxn],s[maxn],d[maxn];

void update(int p,int r,int nod)
{
     if ((p==x) && (r==x)) a[nod]=0;
     else {
                int q=(p+r)/2;
                
                if (x<=q) update(p,q,nod*2);
                else update(q+1,r,nod*2+1);
                
                a[nod]=a[nod*2]+a[nod*2+1];
          }
}

void query(int p,int r,int nod)
{
     if ((x<=p) && ((c-a[nod]>0) || ((c-a[nod]==0) && (p==r))))
     {
         c=c-a[nod];
		 x=d[nod];
     }
	 else {
			 int q=(p+r)/2;

			 if ((c>0) && (x<=q)) query(p,q,nod*2);
			 if (c>0) query(q+1,r,nod*2+1);
		  }
}

int main()
{
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
    
    scanf("%d",&n);
    int aux=n,i;

	l=1;
    while (aux>0)
    {
          aux=aux>>1;
		  l=l<<1;
    }
    
	for (i=l;i<=l+n-1;i++)
	{
    	a[i]=1;
    	d[i]=i-l+1;
    	s[i]=i-l+1;
    }
    
	for (i=l-1;i>0;i--) 
    {
        a[i]=a[i*2]+a[i*2+1];
        s[i]=s[i*2];
		if (d[i*2+1]!=0) d[i]=d[i*2+1];
        else d[i]=d[i*2];
    }
    
	x=2;
	st=1;
    
    for (i=1;i<=n;i++)
    {
        c=i;
        
        query(1,l,1);
        
        if (c>0)
        {
                if (c%a[1]!=0) c=c%a[1];
				else c=a[1];

				x=st;
				query(1,l,1);
        }
                
        printf("%d ",x);
        update(1,l,1);
    }
    
    printf("\n");
    
    return 0;
}