Cod sursa(job #121630)

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

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

int query(int poz)
{
      int 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;
}

int find(int x)
{
      int 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;
    int i,v[NMAX],p;
    
    in=fopen(INF,"r");
    out=fopen(OUF,"w");
    
    fscanf(in,"%d",&n);
    for(i=1;i<=n;++i)
    {
                     fscanf(in,"%d",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,"%d\n",sol[i]);
    
    fclose(in);fclose(out);
    return 0;
}