Cod sursa(job #2920269)

Utilizator Alex_HossuHossu Alexandru Alex_Hossu Data 23 august 2022 13:45:37
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <stdio.h>

#define MAX_N 30005

int aib[MAX_N];
int res[MAX_N];

inline long long int query(int pos) {
  long long int ans = 0;
  while (pos) {
    ans += aib[pos];
    pos -= pos & (-pos);
  }
  return ans;
}

inline void update(int pos, int val, const int &nrn) {
  while (pos <= nrn) {
    aib[pos] += val;
    pos += pos & (-pos);
  }
}

inline long long int interval(int pos1, int pos2) {
  return query(pos2) - query(pos1 - 1);
}


int main () {
  FILE *fin, *fout;
  int n, i, step;
  int pos, last;
  int cont;

  fin = fopen("order.in", "r");

  fscanf(fin, "%d", &n);
  for (i = 1; i <= n; i++)
    update(i, 1, n);

  fclose(fin);

  step = 1; last = 2;
  for (i = 1; i <= n; i++) {
    cont = 0; pos = last;
    while (cont < step) {
      cont += interval(pos, pos);
      pos++;
      if (pos == n + 1)
        pos = 1;
    } --pos;
    if (pos == 0)
      pos = n;
    last = pos;
    res[i] = pos;
    update(pos, -1, n);
    step++;
  }

  fout = fopen("order.out", "w");
  for (i = 1; i <= n; i++)
    fprintf(fout, "%d\n", res[i]);
  fclose(fout);

  return 0;
}