Cod sursa(job #3357757)

Utilizator rapidu36Victor Manz rapidu36 Data 13 iunie 2026 13:52:37
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <fstream>
#include <vector>

using namespace std;

void elibereaza_aib(vector <int> &aib, int poz) {
    int n = (int)aib.size() - 1;
    while (poz <= n) {
        aib[poz]--;
        int p2 = (poz & -poz);
        poz += p2;
    }
}

int putere_2(int n) {
    int p = 1;
    while (p <= n / 2) {
        p *= 2;
    }
    return p;
}

int interogare_aib(vector <int> &aib, int poz) {
    int n = (int)aib.size() - 1;
    // p = cea mai mare poz cu nr de el. libere dinainte < poz
    int p = 0, pas = putere_2(n);
    while (pas > 0) {
        if (p + pas <= n && aib[p+pas] < poz) {
            poz -= aib[p+pas];
            p += pas;
        }
        pas /= 2;
    }
    return p + 1;
}

int main() {
    ifstream in("schi.in");
    ofstream out("schi.out");
    int n;
    in >> n;
    vector <int> poz_ini(n + 1);
    for (int i = 1; i <= n; i++) {
        in >> poz_ini[i];
    }
    in.close();
    vector <int> aib(n + 1);
    for (int i = 1; i <= n; i++) {
        aib[i] = (i & -i);
    }
    vector <int> clasament(n + 1);
    for (int i = n; i >= 1; i--) {
        int poz_clasament = interogare_aib(aib, poz_ini[i]);
        elibereaza_aib(aib, poz_clasament);
        clasament[poz_clasament] = i;
    }
    for (int i = 1; i <= n; i++) {
        out << clasament[i] << "\n";
    }
    out.close();
    return 0;
}