Cod sursa(job #1911286)

Utilizator DanielRusuDaniel Rusu DanielRusu Data 7 martie 2017 20:00:58
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <iostream>
#include <cstdio>

using namespace std;

#define DIM 30005

int N;
int V[DIM], ans[DIM], aib[DIM];

int bin_search(int x);
void update(int pos, int value);
int query(int pos);

int main() {
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);

    scanf("%d\n", &N);

    for(int i = 1; i <= N; ++i) {
        scanf("%d\n", &V[i]);
    }

    for(int i = 1; i <= N; ++i) {
        update(i, 1);
    }

    for(int i = N; i > 0; --i) {
        int pos = bin_search(V[i]) + 1;
        ans[pos] = i;
        update(pos, - 1);
    }

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

    return 0;
}

int bin_search(int x) {
    int pw = 1;

    while(pw <= N) {
        pw <<= 1;
    }

    pw >>= 1;

    int pos = 0;

    while(pw) {
        if(pos + pw <= N) {
            if(query(pos + pw) < x) {
                pos += pw;
            }
        }

        pw >>= 1;
    }

    return pos;
}
void update(int pos, int value) {
    for(;pos < DIM; pos += pos & (-pos)) {
        aib[pos] += value;
    }
}
int query(int pos) {
    int ans = 0;

    for(;pos;pos -= pos & (-pos)) {
        ans += aib[pos];
    }

    return ans;
}