Cod sursa(job #1335361)

Utilizator Athena99Anghel Anca Athena99 Data 5 februarie 2015 14:23:38
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <fstream>

using namespace std;

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

const int nmax= 30000;

int n;
int v[nmax+1], ft[nmax+1], ans[nmax+1];

int bs( int val ) {
    int sol= 0, n2;
    for ( n2= 1; n2<=n; n2*= 2 ) ;
    for ( int step= n2; step>0; step/= 2 ) {
        if ( sol+step<=n && ft[sol+step]<val ) {
            val= val-ft[sol+step];
            sol+= step;
        }
    }

    ++sol;
    return sol;
}

void ft_update( int p, int x ) {
    for ( int i= p; i<=n; i= 2*i-(i&(i-1)) ) {
        ft[i]+= x;
    }
}

int main(  ) {
    fin>>n;
    for ( int i= 1; i<=n; ++i ) {
        ft_update(i, 1);
        fin>>v[i];
    }

    for ( int i= n; i>=1; --i ) {
        int aux= bs(v[i]);
        ans[aux]= i;

        ft_update(aux, -1);
    }

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

    return 0;
}