Cod sursa(job #1086798)

Utilizator tudorv96Tudor Varan tudorv96 Data 18 ianuarie 2014 15:53:27
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <fstream>
using namespace std;

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

const int N = 3e4 + 5;

short aib[N], v[N], sol[N];
int n;

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

short query (int i) {
    short s = 0;
    while (i) {
        s += aib[i];
        i -= i&-i;
    }
    return s;
}

short Bs(int x) {
    int poz = 0;
    for (int step = 1 << 15; step; step >>= 1)
        if (poz + step <= n && query(poz + step) < x)
            poz += step;
    return poz + 1;
}

int main() {
    fin >> n;
    for (int i = 1; i <= n; ++i) {
        fin >> v[i];
        update (i, 1);
    }
    for (int i = n; i; --i) {
        short poz = Bs(v[i]);
        sol[poz] = i;
        update (poz, -1);
    }
    for (int i = 1; i <= n; ++i)
        fout << sol[i] << "\n";
}