Cod sursa(job #1072125)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 3 ianuarie 2014 23:39:15
Problema Schi Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <iostream>
#include <fstream>

using namespace std;

const int Nmax = 30001;

int BIT[Nmax];
int A[Nmax], P[Nmax];
int N;

inline int lsb( int i )
{
    return ( i & ( -i ) );
}

void update( int pos, int val )
{
    for ( int i = pos; i <= N; i += lsb( i ) )
            BIT[i] += val;
}

int query( int pos )
{
    int s = 0;

    for ( int i = pos; i >= 1; i -= lsb( i ) )
            s += BIT[i];

    return s;
}

int cautare( int key )
{
    int st = 1, dr = N, m, gasit = 0;

    while ( st <= dr )
    {
        int m = ( st + dr ) / 2;

        if ( query( m ) < key )
        {
            gasit = m;
            st = m + 1;
        }
        else
        {
            dr = m - 1;
        }
    }

    return gasit;
}

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

    f >> N;

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

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

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

    for ( int i = 1; i <= N; ++i )
            g << P[i] << endl;

    return 0;
}