Cod sursa(job #443454)

Utilizator APOCALYPTODragos APOCALYPTO Data 16 aprilie 2010 23:09:48
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 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<=2*Nu;i+=zeros(i))
  {aib[i]+=val;

  }


}
void Add(int x, int quantity)
{
    int i;

    for (i = x; i <= N+5; i += zeros(i))
        aib[i] += quantity;
}
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<<=i); Nu=i;
    for(i=1;i<=N;i++)
      {fin>>a[i];

      Add(i,1);

      }
    fin.close();
}

int bsearch(int x)
{
int i, step, p=0;;
	for (step=1; step<= N; step<<=1); step>>=1;
    for (i=1; step;step>>=1)
      {//cout<<i;
      if(query(i+step)<=x)
        {i+=step;
        p=1;}




      }
while(query(i-1)==x)
i--;



   return i;
}

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

    cit();
   for(j=1;j<=N;j++)

 for(i=N;i>= 1;i--)
   {
       poz_finala=bsearch(a[i]-1)+1;
   rez[poz_finala]=i;
   neviz[poz_finala]=1;
   update(poz_finala,-1);
   //for(j=1;j<=N;j++)
   //  cout<<aib[j]<<" ";
   // cout<<"\n";

   }
 ofstream fout("schi.out");

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