Cod sursa(job #3190528)

Utilizator not_anduAndu Scheusan not_andu Data 7 ianuarie 2024 17:58:12
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <bits/stdc++.h>

using namespace std;

#define INFILE "schi.in"
#define OUTFILE "schi.out"

const int N_MAX = 30005;

struct Fenwick {

private:
    int n;
    vector<int> aib;

public:

    Fenwick() : n(0) {}
    
    Fenwick(int _n) : n(_n) {
        aib.resize(n + 1, 0);
    }

    void update(int position, int value){
        for(; position <= n; position += (position & -position)) aib[position] += value;
    }

    int query(int position){
        int ans = 0;
        for(; position > 0; position -= (position & -position)) ans += aib[position];
        return ans;
    }

    int find(int target){
        int left = 1, right = n, ans = n;
        while(left <= right){
            int middle = ((left + right) >> 1);
            int value = this->query(middle);
            if(value == target){
                ans = middle, right = middle - 1;
            }
            else if(value > target) right = middle - 1;
            else left = middle + 1;
        }
        return ans;
    }

};

int n, v[N_MAX], ans[N_MAX];

void solve(){

    cin >> n;
    Fenwick aib(n);

    for(int i = 1; i <= n; ++i){
        cin >> v[i]; aib.update(i, 1); 
    }

    for(int i = n; i >= 1; --i){
        int pos = aib.find(v[i]);
        ans[pos] = i;
        aib.update(pos, -1);
    }

    for(int i = 1; i <= n; ++i) cout << ans[i] << '\n';

}

int main(){
    ios_base::sync_with_stdio(false);
    freopen(INFILE, "r", stdin);
    freopen(OUTFILE, "w", stdout);
    cin.tie(0), cout.tie(0);
    solve();
    return 0;
}