Pagini recente » Cod sursa (job #2461893) | Cod sursa (job #373093) | Cod sursa (job #90011) | Cod sursa (job #2245342) | Cod sursa (job #1469195)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
struct Elimin {
vector<int> aib;
int n;
Elimin(int n) : n(n), aib(n + 1) { }
inline void add(int pos) {
while (pos <= n) {
aib[pos]++;
pos += pos ^ (pos & (pos - 1));
}
}
inline int ask1(int pos) {
int sol = 0;
while (pos) {
sol += aib[pos];
pos = pos & (pos - 1);
}
return sol;
}
inline 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 ask1(start + step) - ask1(start);
//return ask(start + 1, start + step);
} else {
int full_laps = (step - (n - start)) / n;
int left = (step - (n - start)) % n;
return
ask1(n) - ask1(start) +
full_laps * ask1(n) +
(left > 0 ? ask1(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 = n * (1 + tostep / (n - tostep + 1));
int minsol = 0, m;
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);
out << (step > 1 ? " " : "") << p;
}
out << "\n";
out.close();
return 0;
}