Cod sursa(job #2019563)

Utilizator rares96cheseliRares Cheseli rares96cheseli Data 8 septembrie 2017 00:59:07
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("schi.in");
ofstream g("schi.out");

int N;

void update(vector < int > &a, int pos, int val) {
    for (; pos <= N; pos += pos & (-pos)) {
        a[pos] += val;
    }
}

int query(vector < int > &a, int pos) {
    int res = 0;
    for (; pos; pos -= pos & (-pos)) {
        res += a[pos];
    }
    
    return res;
}

int main() {
    f >> N;
    vector < int > aib(N + 1), a(N + 1), sol(N + 1);
    
    for (int i = 1; i <= N; ++i) {
        f >> a[i];
        update(aib, i, 1);
    }
    
    for (int i = N; i > 0; --i) {
        int pos = N;
        
        for (int step = (1 << 25); step; step >>= 1) {
            if (pos - step > 0 && query(aib, pos - step) >= a[i]) {
                pos -= step;
            }
        }
        
        sol[pos] = i;
        update(aib, pos, -1);
    }
    
    for (int i = 1; i <= N; ++i) {
        cout << sol[i] << '\n';
    }
    return 0; 
}