Cod sursa(job #2020099)

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

using namespace std;

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

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

int N, aib[30005], a[30005], sol[300005];

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;
    
    for (int i = 1; i <= N; ++i) {
        f >> a[i];
        update(i, 1);
    }
    
    for (int i = N; i > 0; --i) {
        int ps = 0, step = 1;

        for (; step <= N; step <<= 1);
        for (; step; step >>= 1) {
        	if (ps + step <= N && query((ps + step)) <= a[i]) {
        		ps += step;
        	}
        }

        sol[ps] = i;
        update(ps, -1);
    }
    
    for (int i = 1; i <= N; ++i) {
        cout << sol[i] << '\n';
    }
    return 0; 
}