Cod sursa(job #2456592)

Utilizator Tudor06MusatTudor Tudor06 Data 14 septembrie 2019 19:09:06
Problema Schi Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <iostream>
#include <stdio.h>

using namespace std;

int val, poz;
int aint[4 * 30000];
int v[30000];
int rez[30000];

void update( int st, int dr, int i ) {
  if ( st == dr ) {
    aint[i] += val;
  } else {
    int mij = ( st + dr ) / 2;
    if ( poz > mij ) {
      update( mij + 1, dr, i * 2 + 2 );
    } else
      update( st, mij, i * 2 + 1 );
    aint[i] = aint[i * 2 + 1] + aint[i * 2 + 2];
  }
}

int query( int a, int b, int st, int dr, int i ) {
  if ( a == st && b == dr )
    return aint[i];
  else {
    int mij = ( st + dr ) / 2;
    if ( a > mij ) {
      return query( a, b, mij + 1, dr, i * 2 + 2 );
    } else if ( b <= mij ) {
      return query( a, b, st, mij, i * 2 + 1 );
    } else {
      return query( a, mij, st, mij, i * 2 + 1 ) +
             query( mij + 1, b, mij + 1, dr, i * 2 + 2 );
    }
  }
}

int cbin( int val, int n ) {
//  val --;
  int poz = 0, i;
  for ( i = (1 << 15); i > 0; i /= 2 ) {
    if ( poz + i <= n && query( 1, poz + i, 1, n, 0 ) < val ) {
      poz += i;
    }
  }
  return poz + 1;
}

int main() {
  FILE *fin = fopen( "schi.in", "r" ), *fout = fopen( "schi.out", "w" );
  int n, i;
  fscanf( fin, "%d", &n );
  for ( i = 1; i <= n; i ++ ) {
    fscanf( fin, "%d", &v[i] );
    val = 1;
    poz = i;
    update( 1, n, 0 );
  }
  for ( i = n; i > 0; i -- ) {
    val = -1;
    poz = cbin( v[i], n );
    rez[poz] = i;
    update( 1, n, 0 );
  }
  for ( i = 1; i <= n; i ++ )
    fprintf( fout, "%d\n", rez[i] );
  return 0;
}