Cod sursa(job #1701825)

Utilizator cristina_borzaCristina Borza cristina_borza Data 14 mai 2016 11:11:31
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <fstream>
#include <cstdio>

#define NMAX 30000

using namespace std;

int a[NMAX + 5] , aib[NMAX + 5] , sol[NMAX + 5];
int n;

int caut_bin(int val);
int query(int pos);

void update(int pos , int val);

void read(int &x) {
    int sign = 1;
    char ch;
    x = 0;

    while(!isdigit(ch = getchar())) {
        if(ch == '-') {
            sign = -1;
        }

        else {
            sign = 1;
        }
    }

    do {
        x = x * 10 + ch - '0';
    }while(isdigit(ch = getchar()));
    x *= sign;
}

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

    read(n);
    for(int i = 1 ; i <= n ; ++i) {
        read(a[i]);
        update(i , 1);
    }

    for(int i = n ; i >= 1 ; --i) {
        int p = caut_bin(a[i]);
        update(p , -1);
        sol[p] = i;
    }

    for(int i = 1 ; i <= n ; ++i) {
        printf("%d\n" , sol[i]);
    }
    return 0;
}

int caut_bin(int val) {
    int i , p = 0;
    for(i = 1 ; i <= n ; i <<= 1);
    while(i) {
        if(i + p <= n && query(i + p) < val) {
            p += i;
        }

        i >>= 1;
    }

    return p + 1;
}

int query(int pos) {
    int sol = 0;
    while(pos >= 1) {
        sol += aib[pos];
        pos -= pos & ((pos - 1) ^ pos);
    }

    return sol;
}


void update(int pos , int val) {
    while(pos <= n) {
        aib[pos] += val;
        pos += pos & ((pos - 1) ^ pos);
    }
}