Cod sursa(job #1322083)

Utilizator gedicaAlpaca Gedit gedica Data 19 ianuarie 2015 19:24:32
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>
#include <algorithm>

using namespace std;

const int NMAX= 30000;

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

int v[ NMAX+1 ], p[ NMAX+1 ], ai[ 4*NMAX+1 ];

void update( int nod, int st, int dr, int poz, int i )
{
    if ( st == dr )
    {
        ai[ nod ] = 1;
        p[ st ] = i;
        return ;
    }

    int mid = ( st + dr ) / 2;

    if ( mid - st + 1 - ai[ 2 * nod ] >= poz )
    {
        update( 2 * nod, st, mid, poz, i );
    }
    else
    {
        update( 2 * nod + 1, mid + 1, dr, poz - mid + st - 1 + ai[ 2 * nod ], i );
    }

    ai[ nod ] = ai[ 2 * nod ] + ai[ 2 * nod + 1 ];
}
int main()
{
    int N;
    in >> N;

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

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

    for( int i = 1; i <= N; ++ i )
    {
        out << p[i] << ' ';
    }

    return 0;
}