Cod sursa(job #2020093)

Utilizator rares96cheseliRares Cheseli rares96cheseli Data 9 septembrie 2017 13:45:39
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <bits/stdc++.h>

using namespace std;

// #define f cin
// #define g cout

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

int N;
vector < int > aib, a, sol;

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

void update(int pos, int val) {
    for (; pos <= N; pos += lsb(pos)) {
        aib[pos] += val;
    }
}

int query(int pos) {
    int res = 0;
    for (; pos; pos -= lsb(pos)) {
        res += aib[pos];
    }
    
    return res;
}

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