Cod sursa(job #443468)

Utilizator APOCALYPTODragos APOCALYPTO Data 16 aprilie 2010 23:47:47
Problema Schi Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 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)
      {
      if(query(i+step)<=x)
        {i+=step;
        p=1;}




      }
   //cout<<i<<"\n";



   return i;
}

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

    cit();
    aib[0]=1;

int p=1;
 for(i=N;i>= 1;i--)
   {int bula=a[i];
   if(a[i]==1&&p==1)
       {poz_finala=1;
       p=0;}
       else
       poz_finala=bsearch(bula-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;
}