Cod sursa(job #1479447)

Utilizator dorumusuroiFMI - Doru Musuroi dorumusuroi Data 31 august 2015 13:45:09
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <cstdio>

const char iname[] = "schi.in";
const char oname[] = "schi.out";
const int MAXN = 30005;

int n, aib[MAXN], clasat[MAXN], clasament[MAXN];

void update(int index, int val){
    while(index <= n){
        aib[index]+=val;
        index += index &(-index);
    }
}
void initializeAIB(){
    for(int i = 1; i <= n; ++i)
        update(i,1);
}
int find(int val){
    int index = 0;
    int bitmask = 1;
    while(bitmask <= n) bitmask <<=1;
    bitmask >>=1;
    while((bitmask) && (index<=n)){
        int tIndex = index + bitmask;
        if(tIndex <= n){
            if(val == aib[tIndex] && clasament[tIndex]==0) return tIndex;
            else if(val > aib[tIndex]){
                index += bitmask;
                val -= aib[tIndex];
            }
        }
        bitmask >>=1;
    }
    return index;
}

void read(){
    freopen(iname, "r", stdin);
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i){
        scanf("%d", clasat+i);
    }
}

void solve(){
    for(int i = n; i > 0; --i){
        int aux = find(clasat[i]);
        clasament[aux] = i;
        update(aux, -1);
    }
    freopen(oname, "w", stdout);
    for(int i = 1; i <= n; ++i)
        printf("%d\n", clasament[i]);
}

int main()
{
    read();
    initializeAIB();
    solve();
    return 0;
}