Cod sursa(job #1311431)

Utilizator DjokValeriu Motroi Djok Data 8 ianuarie 2015 10:08:45
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include<fstream>
#include<algorithm>
using namespace std;

int i,n,gmb,st,dr,pivot,aib[30005],a[30005],rs[30005];

void update(int poz,int aux) {
     while(poz<=n) aib[poz]+=aux,poz+=-poz&poz;
}

int query(int poz) {
    int ans=0;
    while(poz>=1) ans+=aib[poz],poz-=-poz&poz;
    return ans;
}

int main()
{
  ifstream cin("schi.in");
  ofstream cout("schi.out");

  cin>>n;
  for(i=1;i<=n;++i) cin>>a[i],update(i,1);

  for(i=n;i>=1;--i)
  {
    st=1; dr=n;
    while(st<=dr)
    {
      pivot=(st+dr)/2; gmb=query(pivot);
      if(gmb==a[i] && !rs[pivot]) rs[pivot]=i,st=dr+1,update(pivot,-1);
      else if(gmb<a[i]) st=pivot+1;
           else dr=pivot-1;
    }
  }

  for(i=1;i<=n;++i) cout<<rs[i]<<'\n';

 return 0;
}