Cod sursa(job #567826)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 30 martie 2011 15:09:59
Problema Order Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <cstdio>

const int N = 30005;

int n, poz[N], ai[2 * N];

void read() {
  freopen("order.in", "r", stdin);
  freopen("order.out", "w", stdout);

  scanf("%d", &n);
}

void init(int nod, int p, int u) {
  ai[nod] = u - p + 1;
  if (p == u) {
    poz[p] = nod;
    return;
  }
  int m = (p + u) / 2;
  init(2 * nod, p, m);
  init(2 * nod + 1, m + 1, u);
}

int search(int nod, int p, int u, int val) {
  if (p == u)
    return p;
  int m = (p + u) / 2;
  if (ai[2 * nod] < val)
    return search(2 * nod + 1, m + 1, u, val - ai[2 * nod]);
  return search(2 * nod, p, m, val);
}

void propaga(int nod) {
  ai[nod] --;
  if (nod == 1)
    return;
  propaga(nod / 2);
}

void solve() {
  int lastp, newp, afis;
  lastp = 1;
  for (int i = 1; i <= n; ++ i) {
    newp = (lastp + i) % (n - i + 1);
    if (newp == 0)
        newp = n - i + 1;
    afis = search(1, 1, n, newp);
    propaga(poz[afis]);
    printf("%d ", afis);
    lastp = newp - 1;
  }
  printf("\n");
}

int main() {
  read();
  init(1, 1, n);
  solve();
  return 0;
}