Cod sursa(job #2053648)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 1 noiembrie 2017 00:04:14
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <fstream>
#define DIM 30002

using namespace std;

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

int n, v[DIM], vsort[DIM], aib[DIM];

void update(int nod, int val){
    for(; nod <= n; nod += (nod & -nod))
        aib[nod] += val;
}

int query(int nod){
    int s = 0;
    for(; nod >= 1; nod -= (nod & -nod))
        s += aib[nod];
    return s;
}

int main()
{
    f>>n;
    for(int i = 1; i <= n; ++ i){
        f>>v[i];
        update(i, 1);
    }
    for(int i = n; i >= 1; -- i){
        int st = 1;
        int dr = n;
        while(st <= dr){
            int mid = (st + dr) / 2;
            if(query(mid) < v[i])
                st = mid + 1;
            else
                dr = mid - 1;
        }
        vsort[st] = i;
        update(st, -1);
    }
    for(int i = 1; i <= n; ++ i)
        g<<vsort[i]<<'\n';
    return 0;
}