Cod sursa(job #1464725)

Utilizator andreey_047Andrei Maxim andreey_047 Data 24 iulie 2015 13:03:44
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include<cstdio>
#define nmax 31000
int a[nmax],v[nmax],AIB[nmax],N;
inline void update(int poz,int val)
{
    int i=0,j;
    while(poz<=N)
    {
        AIB[poz]+=val;
        while((poz&(1<<i))==0)
            i++;
        poz+=(1<<i);
        ++i;
    }
}
inline int Compute(int poz)
{
    int s=0,i=0;
    while(poz)
    {
        s+=AIB[poz];
        while((poz&(1<<i))==0)
            i++;
        poz-=(1<<i);
        i++;
    }
    return s;
}
int main(){
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);
    int i,st,dr;
    scanf("%d\n",&N);
    for(i=1;i<=N;i++){
        scanf("%d\n",&a[i]);
        update(i,1);
    }
    i = N;
    while(i){
         st=1;dr=N;
        while(st<=dr){
            int mij=(st+dr)/2;
            if(Compute(mij)>=a[i])
                dr=mij-1;
            else
                st=mij+1;
        }
        update(st,-1);
        v[st]=i;
        --i;
    }
    for(i = 1;i <= N; ++i)
        printf("%d\n",v[i]);
  return 0;
}