Cod sursa(job #2669213)

Utilizator andreitabaraandrei2004 andreitabara Data 6 noiembrie 2020 14:35:32
Problema Schi Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <fstream>

using namespace std;
ifstream in ("schi.in");
ofstream out ("schi.out");
long aib[30002],v[30002],n,i,nr,x,c[30002];
void adaug (int a,int b)
{
    int i;
    for(i=b;i<=n;i+=(i&(-i)))
    aib[i]+=a;
}
int suma (int x)
{
    int s=0,i;
    for(i=x;i>=1;i-=(i&(-i)))
    {
        s+=aib[i];
    }
    return s;
}
int cbin(int x)
{
    int st,dr,mij,sol=0;
    st=1;
    dr=n;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(suma(mij)>=x)
        {
            sol=mij;
            dr=mij-1;
        }
        else st=mij+1;
    }
    return sol;
}

int main()
{
  in>>n;
  for(i=1;i<=n;i++)
  {
      in>>c[i];
      adaug(1,i);
  }
  for(i=n;i>=1;i--)
  {
      nr=cbin(c[i]);
      v[nr]=i;
      adaug(-1,nr);
  }
  for(i=1;i<=n;i++)
  {
      out<<v[i]<<'\n';
  }
    return 0;
}