Cod sursa(job #1060285)

Utilizator RaduGabriel2012Dinu Radu RaduGabriel2012 Data 17 decembrie 2013 20:17:47
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("schi.in");
ofstream g("schi.out");
 int n;
 short a[65605],v[30005],sol[30005],res,qres=0,lt,rt,up,k;

 void Update(int nod)
 { int m;
   if (lt==rt) a[nod]++;
    else
    { m=(lt+rt)/2;
      if (up<=m) { rt=m; Update(2*nod);}
       else {lt=m+1; Update(2*nod+1); }
        a[nod]=a[2*nod]+a[2*nod+1];
    }
 }

 int Bsearch()
 { int i,st=1,dr=n,nod=1,m,nr;
    while(st!=dr)
    { m=(st+dr)/2;
       nr=(m-st+1)-a[2*nod];
      if  (k>nr) {st=m+1; k-=nr; nod=nod*2+1;}
       else {dr=m; nod*=2;}
    }
   return st;
 }

int main()
{ int i;
   f>>n;
  for(i=1;i<=n;i++)
   f>>v[i];

  for(i=n;i>=1;i--)
  { k=v[i]; res=Bsearch();
      sol[res]=i;
       lt=1; rt=n; up=res;
     Update(1);
  }
   for(i=1;i<=n;i++)
    g<<sol[i]<<"\n";
    return 0;
}