Cod sursa(job #2783375)

Utilizator TghicaGhica Tudor Tghica Data 14 octombrie 2021 12:45:10
Problema Schi Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <fstream>

using namespace std;

struct elem{
  short int parinte, copilStanga, copilDreapta, s;
}v[60001];

short int poz[30001], rez[30001], pow, rasp;

void construct( int x, int sum ) {

  v[x].s = sum;
  v[x].parinte = x / 2;
  v[x].copilStanga = x * 2;
  v[x].copilDreapta = x * 2 + 1;
  if( sum == 1 )
    return;
  construct( x * 2, sum / 2 );
  construct( x * 2 + 1, sum / 2 );
  return;
}

void findPoz( int zero, int x ) {
  int a;
  if( x >= pow ) {
    rasp = x;
    return;
  }
  if( zero <= v[v[x].copilStanga].s ) {
    a = v[x].copilStanga;
  } else {
    zero -= v[v[x].copilStanga].s;
    a = v[x].copilDreapta;
  }
  findPoz( zero, a );
}

void updateScadere( int x ) {
  if( x == 1 )
    return;
  v[x].s--;
  updateScadere( x / 2 );
}

int main() {
  ifstream cin("schi.in");
  ofstream cout("schi.out");
  int n, i, x;
  cin>>n;
  for( i = 1; i <= n; i++ ) {
    cin>>poz[i];
  }
  pow = 1;
  while( pow < n )
    pow *= 2;
  construct( 1, pow );
  for( i = n; i >= 1; i-- ) {
    findPoz( poz[i], 1 );
    x = rasp;
    updateScadere( x );
    rez[x - pow + 1] = i;
  }
  for( i = 1; i <= n; i++ )
    cout<<rez[i]<<"\n";
  return 0;
}