Cod sursa(job #2831562)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 11 ianuarie 2022 18:04:22
Problema Order Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <fstream>

using namespace std;

const int N = 3e4 + 5;
const int P2MAX = (1 << 14);

int aib[N], n;
bool afisat[N];

int zeros(int x) {
  return x & (-x);
}

void update(int poz, int add) {
  while (poz <= n) {
    aib[poz] += add;
    poz += zeros(poz);
  }
}

int cbin(int val, int& remaining) {
  int poz = 0;
  for (int p2 = P2MAX; p2 > 0; p2 >>= 1)
    if (poz + p2 <= n && aib[poz + p2] < val) {
      val -= aib[poz + p2];
      poz += p2;
    }
  remaining = val - (poz != n);
  return poz + 1;
}

int main() {
  ifstream cin("order.in");
  ofstream cout("order.out");
  cin >> n;
  cin.close();
  for (int i = 1; i <= n; ++i)
    update(i, 1);
  int sar = 1;
  for (int i = 1; i <= n - 1; ++i) {
    sar = sar + i % (n - i + 1);
    int rest;
    int poz = cbin(sar, rest);
    while (rest > 0) {
      sar = rest;
      poz = cbin(sar, rest);
    }
    update(poz, -1);
    --sar;
    afisat[poz] = true;
    cout << poz << " ";
  }
  int ct = 0;
  for (int i = 1; i <= n; ++i)
    if (!afisat[i]) {
      cout << i << "\n";
      ++ct;
    }
  cout.close();
  return 0;
}