Cod sursa(job #1072131)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 3 ianuarie 2014 23:48:44
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <iostream>
#include <fstream>

using namespace std;

const int Nmax = 30001;

int AINT[4 * Nmax];
int A[Nmax], P[Nmax];
int N;

void update( int nod, int st, int dr, int pos, int value )
{
    if ( st == dr )
    {
        AINT[nod] = value;
    }
    else
    {
        int m = ( st + dr ) / 2;

        if ( pos <= m ) update( 2 * nod, st, m, pos, value );
        else            update( 2 * nod + 1, m + 1, dr, pos, value );

        AINT[nod] = AINT[2 * nod] + AINT[2 * nod + 1];
    }
}

int query( int nod, int st, int dr, int value )
{
    if ( st == dr )
    {
        return st;
    }
    else
    {
        int m = ( st + dr ) / 2;

        if ( value <= AINT[2 * nod] )
                return query( 2 * nod, st, m, value );
        else
                return query( 2 * nod + 1, m + 1, dr, value - AINT[2 * nod] );
    }
}

int main()
{
    ifstream f("schi.in");
    ofstream g("schi.out");

    f >> N;

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

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

    for ( int i = N; i >= 1; i-- )
    {
        int pos = query( 1, 1, N, A[i] );

        P[ pos ] = i;
        update( 1, 1, N, pos, 0 );
    }

    for ( int i = 1; i <= N; ++i )
            g << P[i] << "\n";

    return 0;
}