Cod sursa(job #1469153)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 7 august 2015 17:18:14
Problema Order Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.63 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

struct Elimin {
  vector<int> elim,li, lf;
  int n;

  void fill(int i) {
    if (li[i] < lf[i]) {
      li[2 * i + 1] = li[i];
      lf[2 * i + 1] = (li[i] + lf[i]) / 2;
      fill(2 * i + 1);
      li[2 * i + 2] = (li[i] + lf[i]) / 2 + 1;
      lf[2 * i + 2] = lf[i];
      fill(2 * i + 2);
    }
  }

  Elimin(int n) : n(n), elim(4 * n), li(4 * n), lf(4 * n) {
    li[0] = 1;
    lf[0] = n;
    fill(0);
  }

  void add(int pos) {
    int m, i = 0;
    while (li[i] < lf[i]) {
      elim[i]++;
      m = (li[i] + lf[i]) / 2;
      if (pos <= m) {
        i = 2 * i + 1;
      } else {
        i = 2 * i + 2;
      }
    }
    elim[i]++;
  }

  int _ask(int a, int b, int pos) {
    if (a <= li[pos] && lf[pos] <= b)
      return elim[pos];

    if (b < li[pos] || lf[pos] < a)
      return 0;

    return _ask(a, b, 2 * pos + 1) + _ask(a, b, 2 * pos + 2);
  }

  int ask(int a, int b) {
    int sol = _ask(a, b, 0);
    //std::cerr << "#1[" << a << ", " << b << "] = " << sol << std::endl;
    return sol;
  }

  int wrap(int start, int tostep) {
    if (start + tostep <= n) {
      return start + tostep;
    } else {
      int sol = (tostep - (n - start)) % n;
      return sol == 0 ? n : sol;
    }
  }

  int ask_wrap(int start, int step) {
    if (start + step <= n) {
      return ask(start + 1, start + step);
    } else {
      int full_laps = (step - (n - start)) / n;
      int left = (step - (n - start)) % n;
      return
          ask(start + 1, n) +
          full_laps * elim[0] +
          (left > 0 ? ask(1, left) : 0);
    }
  }

  int find_advance(int start, int tostep) {
    // We need to find a step such that step - ask_wrap(start, step) == tostep
    int li = tostep;
    int lf = tostep;
    int minsol = 0, m;
    while (lf - ask_wrap(start, lf) < tostep) lf *= 2;
    while (li <= lf) {
      m = (li + lf) / 2;
      int realstep = m - ask_wrap(start, m);
      //std::cerr << "realstep(" << start << " + " << m << ") = " << realstep << std::endl;
      if (realstep == tostep) {
        minsol = m;
        lf = m - 1;
      } else if (realstep > tostep) {
        lf = m - 1;
      } else {
        li = m + 1;
      }
    }

    //std::cerr << "Retuning " << wrap(start, minsol) << std::endl;
    return wrap(start, minsol);
  }
};

int n, p, step;

int main()
{
  ifstream in("order.in");
  in >> n;
  in.close();
  Elimin e(n);

  ofstream out("order.out");
  for (p = 1, step = 1; step <= n; ++step) {
    p = e.find_advance(p, step);
    e.add(p);
    //std::cerr << p << std::endl;
    out << (step > 1 ? " " : "") << p;
  }

  out << "\n";
  out.close();

  return 0;
}