Cod sursa(job #3297526)

Utilizator voaidesrVoaides Robert voaidesr Data 22 mai 2025 19:13:34
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <bits/stdc++.h>
using namespace std;

struct Fenwick {
    int n;
    vector<int> bit;
    Fenwick(int n) : n(n), bit(n + 1, 0) {}
    void add(int idx, int delta) {
        for (int i = idx; i <= n; i += i & -i)
            bit[i] += delta;
    }
    int sum(int idx) const {
        int s = 0;
        for (int i = idx; i; i -= i & -i)
            s += bit[i];
        return s;
    }
    int kth(int k) const {
        int pos = 0, step = 1;
        while (step << 1 <= n)
            step <<= 1;
        for (int p = step; p; p >>= 1) {
            int nxt = pos + p;
            if (nxt <= n && bit[nxt] < k) {
                k  -= bit[nxt];
                pos = nxt;
            }
        }
        return pos + 1;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    vector<int> pos(N + 1);
    for (int i = 1; i <= N; ++i)
        fin >> pos[i];

    Fenwick ft(N);
    for (int i = 1; i <= N; ++i)
        ft.add(i, 1);

    vector<int> ans(N + 1);
    for (int i = N; i >= 1; --i) {
        int k = pos[i];
        int loc = ft.kth(k);
        ans[loc] = i;
        ft.add(loc, -1);
    }

    for (int loc = 1; loc <= N; ++loc)
        fout << ans[loc] << '\n';

    return 0;
}