Cod sursa(job #1558253)

Utilizator stoianmihailStoian Mihail stoianmihail Data 28 decembrie 2015 22:03:16
Problema Order Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <stdio.h>

#define aibSize 32768
#define NIL -1

int N;
int aib[aibSize + 1];

/**  Adauga valoarea "x" in aib.
  * val = 1: inserare.
  * val = -1: stergere.
**/
void add(int x, int val) {
  do {
    aib[x] += val;
    x += x & -x;
  } while (x <= aibSize);
}

/** Cauta elementul de pe pozitia "val" in aib. **/
int search(int val) {
  int x = 0, interval;
  for (interval = aibSize >> 1; interval; interval >>= 1) {
    if (aib[x + interval] < val) {
      val -= aib[x += interval];
    }
  }
  return x + 1;
}

int main(void) {
  int i, k, key, last = 2;
  FILE *f = fopen("order.in", "r");
  freopen("order.out", "w", stdout);

  /* Citirea datelor. */
  fscanf(f, "%d", &N);
  for (i = 1; i <= N; i++) {
    add(i, 1);
  }
  fclose(f);

  /* Calcularea solutiei si afisarea ei. */
  for (i = 0; i < N; i++) {
    key = (last + i) % (N - i);
    key = !key ? N - i : key;
    k = search(key);
    fprintf(stdout, "%d ", k);

    add(k, NIL);
    last = key;
  }
  fclose(stdout);

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