Cod sursa(job #35371)

Utilizator stef2nStefan Istrate stef2n Data 22 martie 2007 00:07:33
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <stdio.h>

#define infile "schi.in"
#define outfile "schi.out"
#define NMAX 30002
#define DIMMAX 65600

FILE *fin,*fout;
short int sol[NMAX],v[DIMMAX],t[NMAX];
int n,p,POZ;

void build(short int li, short int ls)
  {
   if(li==ls)
     {
      v[p]=1;
      return;
     }
   p=2*p;
   build(li,((int)li+ls)/2);
   p++;
   build(((int)li+ls)/2+1,ls);
   p=p/2;
   v[p]=v[2*p]+v[2*p+1];
  }

int cauta(int li, int ls, int x)
  {
   int n=1;
   while(li<ls)
        if(v[2*n]>=x)
          {
           ls=(li+ls)/2;
           n=2*n;
          }
        else
          {
           li=(li+ls)/2+1;
           x-=v[2*n];
           n=2*n+1;
          }
   return li;
  }

void erase(short int li, short int ls)
  {
   if(li==ls)
     {
      v[p]=0;
      return;
     }
   if(POZ<=(li+ls)/2)
     {
      p=2*p;
      erase(li,((int)li+ls)/2);
     }
   else
     {
      p=2*p+1;
      erase(((int)li+ls)/2+1,ls);
     }
   p/=2;
   v[p]=v[2*p]+v[2*p+1];
  }

void solve()
  {
   int poz;
   p=1;
   build(0,n-1);
   for(int i=n-1;i>=0;i--)
      {
       poz=cauta(0,n-1,t[i]);
       sol[poz]=i+1;
       p=1;
       POZ=poz;
       erase(0,n-1);
      }
  }


int main()
{
int i;
fin=fopen(infile,"r");
fscanf(fin,"%d",&n);
for(i=0;i<n;i++)
   fscanf(fin,"%d",&t[i]);
fclose(fin);
solve();
fout=fopen(outfile,"w");
for(i=0;i<n;i++)
   fprintf(fout,"%d\n",sol[i]);
fclose(fout);
return 0;
}