Cod sursa(job #2776413)

Utilizator cristi_macoveiMacovei Cristian cristi_macovei Data 19 septembrie 2021 18:23:53
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <iostream>
#include <fstream>
#include <cmath>

const int NMAX = 3e4;

int n;
int logMax;

int bit[1 + NMAX];

inline int lsb(int a) {
  return a & -a;
}

void update(int idx, int val) {
  for (; idx <= n; idx += lsb(idx))
    bit[idx] += val;
}

int query(int idx) {
  int ans = 0;
  for (; idx > 0; idx -= lsb(idx))
    ans += bit[idx];
  return ans;
}

int search(int target) {
  int current = 0;
  for (int exp = logMax; exp >= 0; --exp) {
    if (current + (1 << exp) <= n && bit[current + (1 << exp)] < target) {
      current += (1 << exp);
      target -= bit[current];
    }
  }

  return current + 1; 
}

int main() {
  std::ifstream in("order.in");
  std::ofstream out("order.out");

  in >> n;

  for (int i = 1; i <= n; ++i) {
    bit[i] += 1;
    if (i + lsb(i) <= n)
      bit[i + lsb(i)] += bit[i];
  }

  logMax = (int)floor(log2(n));

  int prev = 1;
  for (int k = 1; k <= n; ++k) {
    int remaining = n - k + 1;
    int target = query(prev) + k % remaining;

    if (target > remaining)
      target -= remaining;

    if (target == 0)
      target = remaining;

    prev = search(target);

    out << prev << ' ';

    update(prev, -1);
  }

  return 0;
}