Cod sursa(job #1777051)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 12 octombrie 2016 00:20:50
Problema Schi Scor 100
Compilator cpp Status done
Runda cerculdeinfo-lectia2-arborideintervale Marime 0.81 kb
#include <cstdio>
#define MAXN 30000
int v[MAXN+1];
int ans[MAXN+1];
#define zeros(x) (x&(-x))
int aib[MAXN+1];
int n;
inline void update(int poz,int val){
    int i;
    for(i=poz;i<=n;i+=zeros(i))
       aib[i]+=val;
}
inline int query(int poz){
   int sum=0,i;
   for(i=poz;i>0;i-=zeros(i))
      sum+=aib[i];
   return sum;
}
int main(){
   FILE*fi,*fout;
   int i,rez,pas;
   fi=fopen("schi.in" ,"r");
   fout=fopen("schi.out" ,"w");
   fscanf(fi,"%d " ,&n);
   for(i=1;i<=n;i++){
     fscanf(fi,"%d " ,&v[i]);
     update(i,1);
   }
   for(i=n;i>=1;i--){
       rez=0;
       for(pas=1<<15;pas;pas>>=1)
         if(rez+pas<=n&&query(rez+pas)<v[i])
           rez+=pas;
       ans[rez+1]=i;
       update(rez+1,-1);
   }
   for(i=1;i<=n;i++)
     fprintf(fout,"%d\n" ,ans[i]);
   fclose(fi);
   fclose(fout);
   return 0;
}