Cod sursa(job #606680)

Utilizator crushackPopescu Silviu crushack Data 7 august 2011 21:52:47
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <stdio.h>
#define NMax 60010
const char IN[]="order.in",OUT[]="order.out";

int N;
int arb[4*NMax];

void Update(int poz,int st,int dr,int x,int v)
{
    if (st==dr){
        arb[poz]=v;
        return;
    }
    int m=(st+dr)>>1;

    if ( x <= m ) Update(2*poz,st,m,x,v);
    else          Update(2*poz+1,m+1,dr,x,v);

    arb[poz]=arb[2*poz]+arb[2*poz+1];
}

inline int Query(int K)
{
    int poz=1,st=0,dr=2*N-1;

    while (st!=dr)
    {
        if (K>arb[2*poz])
            K-=arb[2*poz],poz=2*poz+1,st=((st+dr)>>1)+1;
        else
            poz=2*poz,dr=(st+dr)>>1;
    }
    return st;
}

int Query(int poz,int st,int dr,int x,int y)
{
    if ( x<=st && dr<=y )
        return arb[poz];
    int m=(st+dr)>>1,r1=0,r2=0;

    if ( x <= m ) r1=Query(2*poz,st,m,x,y);
    if ( y  > m ) r2=Query(2*poz+1,m+1,dr,x,y);

    return r1+r2;
}

int main()
{
    int i,last,step;
    freopen(IN,"r",stdin);
    scanf("%d",&N);
    fclose(stdin);

    for (i=0;i<2*N;++i) Update(1,0,2*N-1,i,1);

    freopen(OUT,"w",stdout);
    for (i=last=0;i<N;++i)
    {
        step=i%(N-i);
        int r= Query( step + Query(1,0,2*N-1,0,last) + 1);
        if (r>=N) r-=N;

        printf("%d ",r+1);
        Update(1,0,2*N-1,r,0);Update(1,0,2*N-1,N+r,0);
        last=r;
    }
    printf("\n");
    fclose(stdout);fclose(stdin);
    return 0;
}