Cod sursa(job #3364539)

Utilizator prodsevenStefan Albu prodseven Data 5 septembrie 2026 11:40:56
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream cin("schi.in");
ofstream cout("schi.out");

int n;
vector<int> queries, ans;

class FenwickTree {
    vector<int> tree;
    vector<int> arr;
    int size;
    void build_() {
        for (int i = 1 ; i <= n ; ++i) {
            tree[i] = i & -i;
            arr[i] = 1;
        }
    }
    void update_(int pos, int val) {
        for (int i = pos ; i <= n ; i += i & -i) {
            tree[i] += val;
        }
    }
    int query_(int pos) {
        int ans = 0;
        for (int i = pos ; i > 0 ; i -= i & -i) {
            ans += tree[i];
        }
        return ans;
    }
public:
    FenwickTree(int size) {
        this->size = size;
        tree.assign(size + 2, 0);
        arr.assign(size + 2, 0);
        build_();
    }
    void update(int pos, int val) {
        int delta = val - arr[pos];
        update_(pos, delta);
        arr[pos] = val;
    }
    int exact_sum_position(int sum) {
        int ans_idx = 0, current_sum = 0;
        for (int i = 1 << 30 ; i > 0 ; i >>= 1) {
            if (ans_idx + i <= size && current_sum + tree[ans_idx + i] < sum) {
                ans_idx += i;
                current_sum += tree[ans_idx];
            }
        }
        if (ans_idx + 1 > n || query_(ans_idx + 1) != sum) {
            return -1;
        }
        return ans_idx + 1;
    }
};

int main() {
    cin >> n;
    queries.assign(n + 2, 0);
    ans.assign(n + 2, 0);
    for (int i = 1 ; i <= n ; ++i) {
        cin >> queries[i];
    }
    FenwickTree t(n);
    for (int i = n ; i >= 1 ; --i) {
        int pos = t.exact_sum_position(queries[i]);
        ans[pos] = i;
        t.update(pos, 0);
    }
    for (int i = 1 ; i <= n ; ++i) {
        cout << ans[i] << "\n";
    }
    return 0;
}