Cod sursa(job #121628)

Utilizator megabyteBarsan Paul megabyte Data 9 ianuarie 2008 10:48:41
Problema Schi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <cstdio>
#define INF "schi.in"
#define OUF "schi.out"
#define NMAX 32768
using namespace std;

short n,t[NMAX]={0},sol[NMAX]={0};
void insert(short poz,short x)
{
     short p,zt;
     p=poz; zt=0;
     while(p<=n)
     {
          t[p]+=x;
          while((p&(1<<zt))==0) ++zt;
          p+=(1<<zt);
          ++zt;
     }
}

short query(short poz)
{
      short p,zt,rez;
      p=poz; zt=0; rez=0;
      while(p>0)
      {
            rez+=t[p];
            while((p&(1<<zt))==0) ++zt;
            p-=(1<<zt);
            ++zt;
      }
      return rez;
}

short find(short x)
{
      short st,dr,mij,rez;
      st=1;dr=n;rez=NMAX;
      while(st<=dr)
      {
                   mij=(st+dr)/2;
                   if(query(mij)>=x) 
                   {
                                   rez=mij;
                                   dr=mij-1;
                   }
                   else st=mij+1;
      }
      return rez;
}

int main()
{
    FILE *in,*out;
    short i,v[NMAX],p;
    
    in=fopen(INF,"r");
    out=fopen(OUF,"w");
    
    fscanf(in,"%hd",&n);
    for(i=1;i<=n;++i)
    {
                     fscanf(in,"%hd",v+i);
                     insert(i,1);
    }
    //printf("%hd ",query(6));
    //insert(2,-1);
    //printf("%hd",query(6));
    
    for(i=n;i>0;--i)
    {
     //               printf("%hd ",t[i]);
                    p=find(v[i]);
                    sol[p]=i;
                    
                    insert(p,-1);
    }
    //scanf("%hd",&i);
    for(i=1;i<=n;++i)fprintf(out,"%hd\n",sol[i]);
    
    fclose(in);fclose(out);
    return 0;
}