Cod sursa(job #1425862)

Utilizator isav_costinVlad Costin Andrei isav_costin Data 28 aprilie 2015 11:21:06
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <stdio.h>
int n, i, A[120010], p, ind, pos, nodr;

void upd( int nod, int a, int b, int st, int dr )
{
    int mij;
    if( a<=st && dr<=b )
    {
        A[nod]++;
        return;
    }
    mij=st+(dr-st)/2;
    if( a<=mij )
        upd( 2*nod, a, b, st, mij );
    else
        upd( 2*nod+1, a, b, mij+1, dr );
    A[nod]=A[2*nod]+A[2*nod+1];
}

void find( int nod, int p, int st, int dr )
{
    int mij;
    if( st==dr )
    {
        pos=st, nodr=nod;
        return;
    }
    mij=st+(dr-st)/2;
    if( p<=A[2*nod] )
        find( 2*nod, p, st, mij );
    else
        find( 2*nod+1, p-A[2*nod], mij+1, dr );
}

void remove( int nod )
{
    A[nod]--;
    if( nod==1 )
        return;
    else
        remove( nod/2 );
}

int main()
{
    freopen( "order.in", "r", stdin );
    freopen( "order.out", "w", stdout );
    scanf( "%d", &n );
    for( i=1; i<=n; i++ )
        upd( 1, i, i, 1, n );
    ind=n;
    p=2;
    for( i=1; i<=n; i++ )
    {
        ind--;
        find( 1, p, 1, n );
        printf( "%d ", pos );
        remove( nodr );
        p=p+i;
        if( ind!=0 )
            p=(p-1)%ind+1;
    }
    return 0;
}