Cod sursa(job #2112661)

Utilizator alex.cojocaruAlex Cojocaru alex.cojocaru Data 23 ianuarie 2018 19:07:07
Problema Schi Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <stdio.h>

#define NMAX 30001

int v [ NMAX ] ;
int folosit [ NMAX ] ;
int sum[ 4 * NMAX ] ;
int v_final [ NMAX ] ;

void init (int nod, int st, int dr) {
  if (st == dr )
    sum[nod] = folosit[st] ;
  else {
    int mij = ( st + dr ) / 2 ;
    init (2*nod, st, mij ) ;
    init (2*nod+1, mij+1, dr ) ;
    sum[nod] += sum[2*nod] + sum[2*nod+1] ;
  }
}

void update (int nod, int st, int dr, int index ) {
  if (st == dr ) {
    sum[nod] = 0 ;
  //folosit[index] = 0 ;
  }
  else {
    int mij = (st + dr ) / 2 ;
    if (index <= mij )
      update (2*nod, st, mij, index ) ;
    else if (mij <= index )
      update (2*nod+1, mij+1, dr, index ) ;
    sum[nod] = sum[2*nod] + sum[2*nod+1] ;
  }
}

int queryKth(int nod, int st, int dr, int k) {
  if (st == dr) {
    return st;
  } else {
    int mij = (st + dr) / 2;
    if (k <= sum[2 * nod])
      return queryKth(2 * nod, st, mij, k);
    else
      return queryKth(2 * nod + 1, mij + 1, dr, k - sum[2 * nod]);
  }
}


int main() {

  FILE *fin, *fout ;
  fin = fopen ("schi.in", "r" ) ;
  fout = fopen ("schi.out", "w" ) ;

  int n, i, pozinit ;

  fscanf (fin, "%d", &n ) ;

  for (i = 1 ; i <= n ; i++ ) {
    fscanf (fin, "%d", &v[i] ) ;
    folosit[i] = 1 ;
  }

  init (1, 1, n ) ;

  for (i = n ; i > 0 ; i-- ) {
    pozinit = queryKth(1, 1, n, v[i]) ;
    update(1, 1, n, pozinit ) ;
    folosit[pozinit] = 0 ;
    v_final[pozinit] = i ;
  }

  for (i = 1 ; i <= n ; i++ )
    fprintf (fout, "%d\n", v_final[i] ) ;
  return 0;
}