Cod sursa(job #1768131)

Utilizator alittlezzCazaciuc Valentin alittlezz Data 30 septembrie 2016 11:26:59
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <cstdio>
#include <algorithm>
using namespace std;

int v[30005], sol[30005], aib[30005];

void update(int pos, int x, int n){
    for(;pos <= n;pos += pos&(-pos)){
        aib[pos] += x;
    }
}

int query(int pos){
    int ret = 0;
    for(;pos > 0;pos -= pos&(-pos)){
        ret += aib[pos];
    }
    return ret;
}

int binarySearch(int lf, int rg, int x){
    int i,step;
    for(step = 1;step <= rg;step <<= 1);
    for(i = lf-1;step;step >>= 1){
        if(i + step <= rg && query(i + step) <= x){
            i += step;
        }
    }
    return i;
}

int main(){
    freopen("schi.in", "r", stdin);
    freopen("schi.out", "w", stdout);
    int n,i,pos,x;
    scanf("%d", &n);
    for(i = 1;i <= n;i++){
        scanf("%d", &v[i]);
        update(i, 1, n);
    }
    for(i = n;i >= 1;i--){
        pos = binarySearch(1, n, v[i] - 1) + 1;
        sol[pos] = i;
        update(pos, -1, n);
    }
    for(i = 1;i <= n;i++){
        printf("%d\n", sol[i]);
    }
    return 0;
}