Cod sursa(job #855903)

Utilizator bogdan93Grigorescu Bogdan bogdan93 Data 15 ianuarie 2013 19:49:59
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <cstdio>
#include <cstdlib>

#define nmax 30001

int v [ nmax ] , arb [ 3 * nmax ] , poz [ nmax ] ;
int N , pozitie ;

void update ( int nod , int stanga , int dreapta , int a , int b )
{
    if ( stanga == dreapta )
        arb  [ nod ] = b ;
        else
        {
            int mid = ( dreapta + stanga ) / 2 ;
            if ( a <= mid ) update ( 2 * nod , stanga , mid , a , b ) ;
                else update ( 2 * nod + 1 , mid + 1 , dreapta , a , b ) ;
            arb [ nod ] = arb [ 2 * nod ] + arb [ 2 * nod + 1 ] ;
        }
}
void query ( int nod , int stanga , int dreapta , int a )
{
    if ( stanga == dreapta )
        pozitie = stanga ;
        else
        {
            int mid = ( stanga + dreapta ) / 2 ;
            if ( a <= arb [ 2 * nod ] ) query ( 2 * nod , stanga , mid , a ) ;
                else query ( 2 * nod + 1 , mid + 1 , dreapta , a - arb [ 2 * nod ] ) ;
        }
}

int main ()
{
    FILE *fin , *fout ;
    fin = fopen ( "schi.in" , "rt" ) ;
    fout = fopen ( "schi.out" , "wt" ) ;

    fscanf ( fin , "%d" , &N ) ;

    for ( int i = 1 ; i <= N ; i++ )
        fscanf ( fin , "%d" , v + i ) ;


    for ( int i = 1 ; i <= N ; i++ )
        update ( 1 , 1 , N , i , 1 ) ;

    for ( int i = N ; i >= 1 ; i-- )
    {
        query ( 1 , 1 , N , v [ i ] ) ;
        poz [ pozitie ] = i ;
        update ( 1 , 1 , N , pozitie , 0 ) ;
    }

    for ( int i = 1 ; i <= N ; i++ )
        printf ( "%d\n" , poz [ i ] ) ;

    fclose ( fin ) ;
    fclose ( fout ) ;

    return 0 ;

}