Cod sursa(job #242993)

Utilizator katakunaCazacu Alexandru katakuna Data 11 ianuarie 2009 17:23:01
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<stdio.h>

int q,sol[30111],a[30111*4],n,i,v[30111];

void update(int nod,int p, int u,int poz,int val){
int mij=(p+u)>>1;

  if(p == u){
  a[nod] = val;
  return;
  }

  if(poz<=mij)  update(nod<<1,p,mij,poz,val);
  else          update((nod<<1)+1,mij+1,u,poz,val);

  a[nod] = a[nod<<1] + a[(nod<<1)+1] ;
}

int query(int nod, int p,int u,int x){
int mij=(p+u)>>1;

   if(p == u){
   return p;
   }

   if(x <= a[nod<<1]) query(nod<<1,p,mij,x);
   else               query((nod<<1)+1,mij+1,u,x-a[nod<<1]);

}


int main(){


FILE *f=fopen("schi.in","r");
fscanf(f,"%d",&n);
  for(i=1;i<=n;i++)
  fscanf(f,"%d",&v[i]);
fclose(f);


  for(i=1;i<=n;i++)
  update(1,1,n,i,1);


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

FILE *g=fopen("schi.out","w");
  for(i=1;i<=n;i++)
  fprintf(g,"%d\n",sol[i]);
fclose(g);

return 0;
}