Cod sursa(job #2005724)

Utilizator MihaelaCismaruMihaela Cismaru MihaelaCismaru Data 27 iulie 2017 22:33:32
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include<fstream>
using namespace std;
ifstream in("schi.in");
ofstream out("schi.out");
const int DIM = 30001;
int aib[DIM],v[DIM],rez[DIM],n;
void update( int poz, int val ){
    for( int i = poz; i <= n; i += ( i&(-i) )){
        aib[i] += val;
    }
    return;
}
int query( int poz ){
    int ans = 0;
    for( int i = poz; i >= 1; i -= ( i&(-i) ) ){
        ans += aib[i];
    }
    return ans;
}
int i,go,mid,st,dr;
int main(){
    in >> n;
    for( i = 1; i <= n; i ++ ){
        in >> v[i];
        update( i,1 );
    }
    for( i = n; i >= 1; i -- ){
        for( st = 1, dr = n; st <= dr; ){
            mid = ( st + dr ) >> 1;
            go = query( mid );
            if( go < v[i] ){
                st  = mid + 1;
            }
            else{
                dr = mid - 1;
            }
        }
        rez[st] = i;
        update( st, -1 );
    }
    for( i = 1; i <= n; i ++ ){
        out<<rez[i]<<"\n";
    }
    return 0;
}