Cod sursa(job #1476407)

Utilizator stoianmihailStoian Mihail stoianmihail Data 25 august 2015 04:42:06
Problema Schi Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <stdio.h>

#define Smerenie 32768
#define Nadejde 30001

int N;
int a[Nadejde];        // vectorul nostru.
int order[Nadejde];    // clasamentul final.
int aib[Smerenie + 1];

/** Adauga in aib valoarea "val" incepand cu pozitia "x". **/
void add(int x, int val) {
  do {
    aib[x] += val;
    x += x & -x;
  } while (x <= Smerenie);
}

/** Cauta binar suma partiala "val". **/
int bSearch(int val) {
  int x = 0, interval = (Smerenie >> 1);
  while (interval) {
    if (aib[x + interval] < val) {
      val -= aib[x += interval];
    }
    interval >>= 1;
  }
  return x + 1;
}

int main(void) {
  int i;
  FILE *f = fopen("schi.in", "r");

  fscanf(f, "%d\n", &N);
  for (i = 1; i <= N; i++) {
    fscanf(f, "%d", &a[i]);
    add(i, 1);
  }
  fclose(f);

  f = fopen("schi.out", "w");

  /** Determina clasamentul final. **/
  for (i = N; i > 0; i--) {
    int pos = bSearch(a[i]);
    order[pos] = i;
    add(pos, -1);
  }
  for (i = 1; i <= N; i++) {
    fprintf(f, "%d\n", order[i]);
  }
  fclose(f);

  /// Multumim Doamne!
  puts("Doamne ajuta!");
  return 0;
}