Cod sursa(job #3320274)

Utilizator RaresHRares Hanganu RaresH Data 4 noiembrie 2025 19:58:29
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <stdio.h>

const int MAX_N = 30'000;

struct Aib {
  int n;
  int aib[2 * MAX_N + 1];

  void init(int _n) {
    n = _n;
  }

  void set(int pos) {
    for(; pos <= n; pos += pos & -pos) {
      aib[pos]++;
    }
  }

  int query(int pos) {
    int ret = 0;
    for(; pos > 0; pos &= pos - 1) {
      ret += aib[pos];
    }
    return ret;
  }

  int find_idx(int start, int k) {
    int pref_sum = query(start);
    int idx = 0;
    int sum = 0;
    for(int step = (1 << 17); step > 0; step /= 2) {
      if(idx + step <= start) {
        sum += aib[idx + step];
        idx += step;
        continue;
      }
      if(idx + step > n) {
        continue;
      }

      int x = idx + step - start - (sum + aib[idx + step] - pref_sum);
      if(idx + step <= n && x < k) {
        sum += aib[idx + step];
        idx += step;
      }
    }
    return idx + 1;
  }
};

Aib aib;

int main() {
  FILE* fin = fopen("order.in", "r");
  FILE* fout = fopen("order.out", "w");

  int n;
  fscanf(fin, "%d", &n);

  aib.init(2 * n);
  int last = 0;
  for(int i = 0; i < n; i++) {
    int kth = i % (n - i) + 1;
    int idx = (aib.find_idx(last + 1, kth) - 1) % n;
    aib.set(idx + 1);
    aib.set(idx + 1 + n);
    fprintf(fout, "%d ", idx + 1);
    last = idx;
  }

  fprintf(fout, "\n");

  fclose(fin);
  fclose(fout);

  return 0;
}