Cod sursa(job #1769613)

Utilizator CodrutLemeniCodrut Lemeni CodrutLemeni Data 2 octombrie 2016 20:14:40
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define N 30010

using namespace std;

int v[N];
int poz[N];
int arb[N];
int n;

void update(int nod,int val){

    while(nod<=n){
        arb[nod]+=val;
        nod=nod+ ( nod ^ ( nod & ( nod-1 ) ) );
    }
}

//int query( int s){
//    static int k,span;
//
//    for(span=1;span<n;span<<=1);
//
//    for(k=0; span; span>>=1){
//        if(k+span>n){
//            continue;
//        }
//        if(s>= arb[k+span] ){
//            k+=span;
//            s-=arb[k];
//            if(!s){
//                return k;
//            }
//        }
//    }
//    return -1;
//}

int getsum(int x){
    static int s;

    s=0;
    while(x>0){
        s+=arb[x];
        x-=x&(-x);
    }

    return s;
}

int query(int S) {
    int l = 1, r = n;
    int mid, s;
    while (l <= r) {
        mid = (l+r)/2;
        s = getsum(mid);
        if (s < S){
            l = mid+1;
        }else if (s > S){
            r = mid-1;
        }else if (mid > 0 && getsum(mid-1) == S){
          r = mid-1;
        }else
            return mid;
    }
    return -1;
}
int main(){
    int i,k;

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

    scanf("%d",&n);

    for(i=1;i<=n;i++){
        scanf("%d",&v[i]);
        update(i,1);
    }

    for(i=n;i>0;i--){
        k=query( v[i]);
        poz[  k ]= i;
        update(k,-1);
    }

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

    return 0;
}