Cod sursa(job #2474598)

Utilizator Asgari_ArminArmin Asgari Asgari_Armin Data 15 octombrie 2019 16:31:07
Problema Schi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <fstream>

using namespace std;

ifstream fin( "schi.in" );
ofstream fout( "schi.out" );

const int NMAX = 30000;
int v[NMAX + 1];
int sol[NMAX + 1];
int aint[NMAX * 4 + 1];
int s;

void build( int nod, int st, int dr ){
  int med;
  if( st == dr ){
    aint[nod] = v[st];
    return;
  }
  med = (st + dr) >> 1;
  build( nod << 1, st, med );
  build( (nod << 1) | 1, med + 1, dr );
  aint[nod] = aint[nod << 1] + aint[(nod << 1) | 1];
}

int query_bun(int nod, int x, int val)
{
  int st, pas, s=0, i;
  st = 0;
  for(pas=x;pas>0;pas>>=1)
    if(aint[nod<<1]+s<val)
    {
      s += aint[nod<<1];
      nod=((nod<<1)|1);
      st += pas;
    }
    else
      nod<<=1;
  return st + 1;
}

void update( int nod, int st, int dr, int a, int val ){
  int med;
  if( st == dr ){
    aint[nod] = val;
    return;
  }
  med = (st + dr) >> 1;
  if( a <= med )
    update( (nod << 1), st, med, a, val );
  else
    update( (nod << 1) | 1, med + 1, dr, a, val );
  aint[nod] = aint[nod << 1] + aint[(nod << 1) | 1];
}

int main() {
    int n, i, nnou;
    fin >> n;
    nnou = 1;
    while(nnou<n)
      nnou+=nnou;
    n = nnou;
    for( i = 1; i <= n; ++i )
      v[i] = 1;
    build( 1, 1, n );
    for( i = 1; i <= n; ++i )
      fin >> v[i];
    for( i = n; i >= 1; --i ){
        s=query_bun(1, n/2, v[i]);
      sol[s] = i;
      update( 1, 1, n, s, 0 );
    }
    for( i = 1; i <= n; ++i )
      fout << sol[i] << "\n";
    return 0;
}