Cod sursa(job #1874993)

Utilizator robx12lnLinca Robert robx12ln Data 10 februarie 2017 17:14:20
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include<fstream>

using namespace std;

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

int a[30005], n, v[30005], sol[30005], st, dr, mid;

void update( int p, int val ){

    for( ; p <= n; p += (p&(-p)) ){
        a[p] += val;
    }

    return ;

}

int query( int p ){

    int r = 0;

    for( ;p >= 1; p -= (p&(-p)) ){
        r += a[p];
    }

    return r;

}

int main(){

    fin >> n;
    for( int i = 1; i <= n; i++ ){

        fin >> v[i];

        update( i, 1 );

    }

    for( int i = n; i >= 1; i-- ){

        fin >> v[i];

        st = 1;
        dr = n;
        while( st <= dr ){

            mid = ( st + dr ) / 2;

            if( query( mid ) < v[i] ){
                st = mid + 1;
            }else{
                dr = mid - 1;
            }

        }

        sol[st] = i;

        update( st, -1 );

    }

    for( int i = 1; i <= n; i++ ){
        fout << sol[i] << "\n";
    }

    return 0;
}