Cod sursa(job #2783374)

Utilizator TghicaGhica Tudor Tghica Data 14 octombrie 2021 12:41:40
Problema Schi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <fstream>

using namespace std;

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

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

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

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

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-- ) {
    x = findPoz( poz[i], 1 );
    updateScadere( x );
    rez[x - pow + 1] = i;
  }
  for( i = 1; i <= n; i++ )
    cout<<rez[i]<<"\n";
  return 0;
}