Cod sursa(job #1060254)

Utilizator RaduGabriel2012Dinu Radu RaduGabriel2012 Data 17 decembrie 2013 19:44:29
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 m;
    if (lt<=st && dr<=rt) qres+=a[nod];
      else
      { m=(st+dr)/2;
         if (lt<=m) Query(2*nod,st,m);
         if (rt>m) Query(2*nod+1,m+1,dr);
      }
 }

 int Bsearch(int k)
 { int i,st=1,dr=n,m;
    while(st<dr)
    { m=(st+dr)/2;
       qres=0; lt=1; rt=m;
      Query(1,1,n);
       qres=m-qres;
      if (qres>=k) dr=m-1; else st=m+1;
    }
     m=(st+dr)/2;
         qres=0; lt=1; rt=m;
      Query(1,1,n);
       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;
}