Cod sursa(job #70052)

Utilizator sealTudose Vlad seal Data 4 iulie 2007 18:21:26
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include<stdio.h>
#define Nm (1<<15)
#define m ((l+r)>>1)
#define ls (n<<1)
#define rs (n<<1|1)
int Sum[Nm<<1],A[Nm],n;

void read()
{
    freopen("order.in","r",stdin);
    scanf("%d",&n);
}

void build(int n, int l, int r)
{
    Sum[n]=r-l+1;
    if(l<r)
    {
        build(ls,l,m);
        build(rs,m+1,r);
    }
}

int a,b,k,ans;

void querysum(int n, int l, int r)
{
    if(a<=l && r<=b)
        ans+=Sum[n];
    else
    {
        if(a<=m)
            querysum(ls,l,m);
        if(b>m)
            querysum(rs,m+1,r);
    }
}

void query(int n, int l, int r)
{
    if(l==r)
        ans=l;
    else
    {
        if(a<=m)
        {
            ans=0;
            querysum(ls,l,m);
            if(ans<k)
                k-=ans;
            else
            {
                query(ls,l,m);
                return;
            }
        }
        query(rs,m+1,r);
    }
}

void update(int n, int l, int r)
{
    --Sum[n];
    if(l<r)
        if(ans<=m)
            update(ls,l,m);
        else
            update(rs,m+1,r);
}

void solve()
{
    int i;

    build(1,1,n);
    
    A[0]=1;
    for(i=1;i<=n;++i)
    {
        a=A[i-1]+1; b=n; ans=0;
        querysum(1,1,n);
        k=i%(n-i+1);
        if(!k)
            k+=n-i+1;
        if(ans<k)
        {
            a=1;
            b=A[i-1];
            k-=ans;
        }
        query(1,1,n);
        A[i]=ans;
        update(1,1,n);
    }
}

void write()
{
    int i;

    freopen("order.out","w",stdout);
    for(i=1;i<n;++i)
        printf("%d ",A[i]);
    printf("%d\n",A[i]);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}