Cod sursa(job #1760924)

Utilizator blatulInstitutul de Arta Gastronomica blatul Data 21 septembrie 2016 15:50:49
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <fstream>
#include <algorithm>
using namespace std;

#define Nmax 30002
#define LSB(x) ( (x) & -(x) )

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

int N, v[Nmax], AIB[Nmax], Sol[Nmax];
bool Ocupat[Nmax];

inline void AddVal( int pos, int val ){

    for( int i = pos; i <= N; i += LSB(i) )
        AIB[i] += val;
}

inline int GetSum( int pos ){

    int res = 0;

    for( int i = pos; i > 0; i -= LSB(i) )
        res += AIB[i];

    return res;
}

int Bsearch( int val ){

    int st = 1, dr = N;

    while( st <= dr ){
        int mid = ( st + dr ) >> 1;

        int x = GetSum(mid);

        if( x < val ){
            st = mid + 1;
            continue;
        }
        if( x > val ){
            dr = mid - 1;
            continue;
        }
        if( x == val ){
            if( Ocupat[mid] )
                dr = mid - 1;
            else
                return mid;
        }
    }
}

int main(){

    fin >> N;

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

    for( int i = N; i >= 1; --i ){
        int poz = Bsearch(v[i]);
        Sol[poz] = i;
        AddVal( poz, -1 );
        Ocupat[poz] = 1;
    }

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

    return 0;
}