Cod sursa(job #1514443)

Utilizator gedicaAlpaca Gedit gedica Data 31 octombrie 2015 10:59:33
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <fstream>

using namespace std;

const int NMAX = 60028;

ifstream in ( "schi.in" );
ofstream out ( "schi.out" );

int sol [NMAX<<1], v[NMAX<<1], loc[NMAX<<1];
int pos;

void create( int nod , int st , int dr )
{
    if ( st==dr )
    {
        v[nod]= 1;
        return ;
    }
    int mij= ( st+dr ) >> 1 ;

    if ( pos<=mij )
    {
        create( nod<<1 , st , mij );
    }
    else create( (nod << 1) + 1, mij + 1, dr );

    v[ nod ] = v[ nod << 1 ] + v[ (nod << 1)+1 ] ;
}

void upd( int nod , int st , int dr , int poz )
{
    if ( st==dr )
    {
        v[nod] = 0 ;
        sol[st] = pos ;
        return ;
    }

    int mij = ( st+dr ) >> 1 ;

    if ( poz <= v[ nod << 1 ] ){
        upd( nod << 1, st, mij, poz );
    }
    else
    {
        upd( (nod << 1) + 1, mij+1, dr, poz-v[ nod << 1 ] );
    }
    v[nod] = v[ nod << 1 ] + v[ ( nod << 1 ) + 1 ];
}

int main( )
{
    int N;
    in >> N;

    for( int i = 1 ; i <= N ; ++ i )
    {
        pos = i ;
        create( 1 , 1 , N );
    }

    for ( int i = 1 ; i<=N; ++i )
    {
        in >> loc[i] ;
    }

    for ( int i= N ; i>=1 ; --i )
    {
        pos= i ;
        upd( 1 , 1 , N , loc[i] ) ;
    }

    for ( int i= 1 ; i<=N; ++i )
    {
        out << sol [ i ] << '\n' ;
    }
    return 0;
}
//arbore