Cod sursa(job #2920314)

Utilizator Alex_HossuHossu Alexandru Alex_Hossu Data 23 august 2022 16:57:48
Problema Order Scor 85
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <stdio.h>

#define MAX_N 30005

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

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

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

static 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 st, dr, mij;
  int stepCalc, p, q;
  int pos, last;

  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++) {
    st = last; dr = n;
    while (dr - st > 1) {
      mij = (st + dr) / 2;
      if (interval(last, mij) < step)
        st = mij;
      else
        dr = mij;
    }

    p = interval(last, n);
    if (p < step) {
      stepCalc = step - p;
      while (stepCalc > 0) {
        st = 0, dr = n;
        while (dr - st > 1) {
          mij = (st + dr) / 2;
          if (interval(1, mij) < stepCalc)
            st = mij;
          else
            dr = mij;
        }
        q = stepCalc - interval(1, st);
        if (q > 0)
          stepCalc -= interval(1, n);
        else
          stepCalc = q;
      }
    }

    if (interval(last, st) < step)
      st++;

    pos = st;
    last = pos;
    res[i] = pos;
    update(pos, -1, n);
    step++;
  }

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

  return 0;
}