Cod sursa(job #1695944)

Utilizator DysKodeTurturica Razvan DysKode Data 28 aprilie 2016 00:50:30
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <fstream>

using namespace std;

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

int arbint[ 4 * 30010 ], i,j,n,m,k,v[30010],ans[30010],x;

void update( int nod, int left, int right, int src, int val )
{
    int middle = ( left + right ) / 2;
    if( left == right )
    {
        arbint[ nod ] = val;
        return;
    }
    if( src <= middle )
        update( 2 * nod , left , middle , src , val );
    else
        update( 2 * nod + 1 , middle + 1 , right , src , val );
    arbint[ nod ] = arbint[ 2 * nod ] + arbint[ 2 * nod + 1 ];
}

int go( int nod, int left, int right, int src )
{
    int middle = ( left + right ) / 2;
    if( left == right )
        return left;
    if( arbint[ nod ] == src )
    {
        if( arbint[ 2 * nod + 1 ] )
            return go( 2 * nod + 1 , middle + 1 , right , src - arbint[ 2 * nod ] );
        else
            return go( 2 * nod , left , middle , src );
    }
    else
    {
        if( arbint[ 2 * nod ] >= src )
            return go( 2 * nod , left , middle , src );
        else
            return go( 2 * nod + 1 , middle + 1 , right , src - arbint[ 2 * nod ] );
    }
}

int main()
{
    fin>>n;
    for( i = 1 ; i <= n ; i++ )
    {
        fin>>v[ i ];
        update( 1 , 1 , n , i , 1 );
    }

    for( i = n ; i >= 1 ; i-- )
    {
        x = go( 1 , 1 , n , v[ i ] );
        ans[ x ] = i;
        update( 1 , 1 , n , x , 0 );
    }

    for( i = 1 ; i <= n ; i++ )
    {
        fout<<ans[ i ]<<'\n';
    }

return 0;
}