Cod sursa(job #3311929)

Utilizator pkseVlad Bondoc pkse Data 24 septembrie 2025 22:58:23
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
/*

    https://x.com/70lunaa/status/1970611853005816105

*/
#include <bits/stdc++.h>
using namespace std;

int lsb(int x) {
    return x & (-x);
}

struct AIB {
    vector<int> a;
    int n;

    AIB(int N) {
        n = N;
        a.resize(n);
    }

    void update(int p, int val) {
        for(; p <= n; p += lsb(p)) {
            a[p - 1] += val;
        }
    }

    int pf(int p) {
        int ans = 0;
        for(; p > 0; p -= lsb(p)) {
            ans += a[p - 1];
        }
        return ans;
    }
};

int main() {
    freopen("schi.in", "r", stdin);
    freopen("schi.out", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n; cin >> n;

    vector<int> a(n), b(n);
    AIB aib(n);

    for(int i = 0; i < n; i ++) {
        cin >> a[i];
    }

    reverse(a.begin(), a.end());

    for(int i = 0; i < n; i ++) {
        int st = 1, dr = n, ans;
        while(st <= dr) {
            int mj = (st + dr) / 2;
            int rez = mj - aib.pf(mj);
            if(rez < a[i]) {
                st = mj + 1;
            } else {
                ans = mj;
                dr = mj - 1;
            }
        }
        aib.update(ans, 1);
        b[ans - 1] = n - i;
    }
    
    for(int i = 0; i < n; i ++) {
        cout << b[i] << '\n';
    }
}