Cod sursa(job #1438369)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 19 mai 2015 19:40:43
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include<cstdio>
using namespace std;
int aib[30001],v[30001],vc[30001],n;
int sum(int poz){
    int s=0;
    while(poz>0){
        s+=aib[poz];
        poz=poz-((poz&(poz-1))^poz);
    }
    return s;
}
int add(int poz,int val){
    while(poz<=n){
        aib[poz]+=val;
        poz=poz+((poz&(poz-1))^poz);
    }
}
int main(){
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);
    int i,l1,l2,m,x,mij;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&v[i]);
        add(i,1);
    }
    for(i=n;i>=1;i--){
        l1=1;
        l2=n;
        m=1000000;
        while(l1<=l2){
            mij=(l1+l2)/2;
            x=sum(mij);
            if(x==v[i]&&aib[mij]!=0&&mij<m)
                m=mij;
            if(x>=v[i])
                l2=mij-1;
            else
                l1=mij+1;
        }
        vc[m]=i;
        add(m,-1);
    }
    for(i=1;i<=n;i++)
        printf("%d\n",vc[i]);
	return 0;
}