Cod sursa(job #876515)

Utilizator MagnvsDaniel Constantin Anghel Magnvs Data 11 februarie 2013 21:12:22
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <stdio.h>
 
int a[100001],b[100001];
 
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 ",b[i]);
    return 0;
}