Cod sursa(job #1060250)

Utilizator RaduGabriel2012Dinu Radu RaduGabriel2012 Data 17 decembrie 2013 19:42:20
Problema Schi Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 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;

 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];
    }
 }

 void Query(int nod,int st,int dr,int x,int y)
 { int m;
    if (x<=st && dr<=y) qres+=a[nod];
      else
      { m=(st+dr)/2;
         if (x<=m) Query(2*nod,st,m,x,y);
         if (y>m) Query(2*nod+1,m+1,dr,x,y);
      }
 }

 int Bsearch(int k)
 { int i,st=1,dr=n,m;
    while(st<dr)
    { m=(st+dr)/2;
       qres=0;
      Query(1,1,n,1,m);
       qres=m-qres;
      if (qres>=k) dr=m-1; else st=m+1;
    }
     m=(st+dr)/2;
         qres=0;
      Query(1,1,n,1,m);
       qres=m-qres;
    if (qres!=k) m++;
   //cout<<m<<"\n";
   return m;
 }
int main()
{ int i;
   f>>n;
  for(i=1;i<=n;i++)
   f>>v[i];

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