# Cod sursa(job #1469153)

Utilizator Data 7 august 2015 17:18:14 Order 80 cpp done Arhiva de probleme 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);
}

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
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) {