Cod sursa(job #2334201)

Utilizator ApostolIlieDanielApostol Daniel ApostolIlieDaniel Data 2 februarie 2019 12:20:25
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <bits/stdc++.h>

using namespace std;

#define chestie(x) x&(-x)

const int MAXN = 30000;

int aib[MAXN + 1];
int n;
void update (int poz, int val) {
  while (poz <= n) {
    aib[poz] += val;
    poz += chestie (poz);
  }
}

int query (int poz) {
  int sol = 0;
  while (poz) {
    sol += aib[poz];
    poz -= chestie (poz);
  }
  return sol;
}

int find (int val) {
  int x = 0;
  int interval = (1 << 20);
  while (interval) {
    if (x + interval <= n && aib[x + interval] < val) {
      val -= aib[x + interval];
      x += interval;
    }
    interval >>= 1;
  }
  return x + 1;
}

int main() {
  int i, val, poz;
  freopen ("order.in", "r", stdin);
  freopen ("order.out", "w", stdout);
  scanf ("%d", &n);
  for (i = 1; i <= n; i++)
    update (i, 1);
  val = 2;
  for (i = 1; i <= n; i++) {
    val = (val - 2 + i) % (n - i + 1) + 1;
    poz = find (val);
    update (poz, -1);
    printf ("%d ", poz);
  }
  return 0;
}