Cod sursa(job #2753170)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 21 mai 2021 13:09:09
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <fstream>
#include <cmath>

using namespace std;

const int N = 30000;

int loc[N + 1], aib[N + 1], rez[N + 1], n, p2;

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

int caut(int val) {
    int poz = 0, pas = p2;
    while (pas) {
        if (poz + pas <= n && aib[poz + pas] < val) {
            val -= aib[poz + pas];
            poz += pas;
        }
        pas /= 2;
    }
    return poz + 1;
}

int main() {
    ifstream in("schi.in");
    ofstream out("schi.out");
    in >> n;
    for (int i = 1; i <= n; ++i) {
        in >> loc[i];
        update(i, 1);
    }
    in.close();
    p2 = (1 << (int)log2(n));
    for (int i = n; i >= 1; --i) {
        int poz = caut(loc[i]);
        update(poz, -1);
        rez[poz] = i;
    }
    for (int i = 1; i <= n; ++i)
        out << rez[i] << '\n';
    out.close();
    return 0;
}