Cod sursa(job #443476)

Utilizator APOCALYPTODragos APOCALYPTO Data 17 aprilie 2010 00:03:14
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include<iostream>
#include<fstream>
using namespace std;
int N,aib[30005],a[30005],rez[30005],neviz[30005],Nu;
#define zeros(x) ( (x ^ (x - 1)) & x )
void update(int p,int val)
{
int i;
for(i=p;i<=N;i+=zeros(i))
  {aib[i]+=val;

  }


}

int  query(int p)
{int sum=0;

    for(;p!=0;p-=((p ^ (p-1)) & p))
    sum+=aib[p];

    return sum;

}

void cit()
{int i;
    ifstream fin("schi.in");
    fin>>N;

    for(i=1;i<=N;i++)
      {fin>>a[i];
       update(i,1);


      }
    fin.close();
}

int bsearch(int x)
{
int i, step, p=0;

	for (step=1; step<= N; step<<=1);step>>=1;
    for (i=N; step;step>>=1)
      {
      if(i-step>=1)
      if(query(i-step)>=x)
        {i-=step;
        }
      }




   return i;
}

int main()
{int i,poz_finala,j;

    cit();
    aib[0]=1;

int p=1;
 for(i=N;i>= 1;i--)
   {
       poz_finala=bsearch(a[i]);

   rez[poz_finala]=i;

   update(poz_finala,-1);


   }
 ofstream fout("schi.out");

 for(i=1;i<=N;i++)
    fout<<rez[i]<<"\n";
    fout.close();
    return 0;
}