Cod sursa(job #1992747)

Utilizator DruffbaumPopescu Vlad Druffbaum Data 21 iunie 2017 12:23:17
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <cstdio>

const int MAXN = 3e4;

int aib[MAXN + 1];

inline void add(int x, int val, int n) {
  while (x <= n) {
    aib[x] += val;
    x += x & -x; 
  }
}

inline int sum(int x) {
  int s = 0;
  while (x) {
    s += aib[x];
    x -= x & -x;
  }
  return s;
}

int main() {
  int n, st, dr, x, mid, poz;
  FILE *f = fopen("order.in", "r");
  fscanf(f, "%d", &n);
  fclose(f);
  for (int i = 1; i <= n; ++i) {
    add(i, 1, n);
  }
  poz = 2;
  f = fopen("order.out", "w");
  for (int i = 1; i <= n; ++i) {
    poz = (poz + i - 1) % (n - i + 1);
    if (!poz) {
      poz = n - i + 1;
    }
    st = 1;
    dr = x = n;
    while (st <= dr) {
      mid = (st + dr) >> 1;
      if (sum(mid) <= poz) {
        x = mid;
        st = mid + 1;
      } else {
        dr = mid - 1;
      }
    }
    while (sum(x) == poz) {
      --x;
    }
    ++x;
    add(x, -1, n);
    fprintf(f, "%d ", x);
  }
  fclose(f);
  return 0;
}