Cod sursa(job #2777776)

Utilizator cyg_dawidDavid Ghiberdic cyg_dawid Data 24 septembrie 2021 13:10:45
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>
#include <vector>

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

int const nmax = 30000;
int aib[nmax];
std::vector <int> v, poz;
int n;

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

int sum (int x) {
    int sum = 0;
    for (int i = x; i > 0; i -= (i & -i))
        sum += aib[i];
    return sum;
}

int bs (int x) {
    int st = 1, dr = n + 1;
    while (st < dr) {
        int med = (st + dr) >> 1;
        if (sum (med) < x)
            st = med + 1;
        else
            dr = med;
    }
    return dr;
}

int main() {
    fin >> n;
    v.resize(n + 1);
    poz.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        fin >> v[i];
        update (i, 1);
    }
    for (int i = n; i > 0; i--) {
        int position = bs (v[i]);
        poz[position] = i;
        update(position, -1);
    }
    for (int i = 1; i <= n; i++)
        fout << poz[i] << "\n";
    return 0;
}