Cod sursa(job #2020157)

Utilizator rares96cheseliRares Cheseli rares96cheseli Data 9 septembrie 2017 14:47:29
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 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 = 0;
         
        for (int step = (1 << 25); step; step >>= 1) {
            if (pos + step <= N && query(aib, pos + step) <= a[i]) {
                pos += step;
            }
        }
         
        sol[pos] = i;
        update(aib, pos, -1);
    }
     
    for (int i = 1; i <= N; ++i) {
        g << sol[i] << '\n';
    }
    return 0; 
}