Cod sursa(job #35351)

Utilizator stef2nStefan Istrate stef2n Data 21 martie 2007 23:46:22
Problema Schi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 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];
int n,p,poz,k;

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];
  }

short int cauta(short int li, short int ls)
  {
   if(li==ls)
     return li;
   if(v[2*p]>=poz)
     {
      p=2*p;
      return cauta(li,((int)li+ls)/2);
     }
   else
     {
      p=2*p+1;
      poz-=v[p-1];
      return cauta(((int)li+ls)/2+1,ls);
     }
  }

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);
      p/=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 x;
   if(!k)
     return;
   fscanf(fin,"%d",&x);
   k--;
   solve();
   k++;
   p=1;
   poz=x;
   x=cauta(0,n-1);
   sol[x]=n-k+1;
   p=1;
   poz=x;
   erase(0,n-1);
  }


int main()
{
fin=fopen(infile,"r");
fscanf(fin,"%d",&n);
p=1;
build(0,n-1);
k=n;
solve();
fclose(fin);

fout=fopen(outfile,"w");
for(int i=0;i<n;i++)
   fprintf(fout,"%d\n",sol[i]);
fclose(fout);
return 0;
}