Pagini recente » Cod sursa (job #1953795) | Cod sursa (job #572934) | Cod sursa (job #1167494) | Cod sursa (job #1243462) | Cod sursa (job #2776413)
#include <iostream>
#include <fstream>
#include <cmath>
const int NMAX = 3e4;
int n;
int logMax;
int bit[1 + NMAX];
inline int lsb(int a) {
return a & -a;
}
void update(int idx, int val) {
for (; idx <= n; idx += lsb(idx))
bit[idx] += val;
}
int query(int idx) {
int ans = 0;
for (; idx > 0; idx -= lsb(idx))
ans += bit[idx];
return ans;
}
int search(int target) {
int current = 0;
for (int exp = logMax; exp >= 0; --exp) {
if (current + (1 << exp) <= n && bit[current + (1 << exp)] < target) {
current += (1 << exp);
target -= bit[current];
}
}
return current + 1;
}
int main() {
std::ifstream in("order.in");
std::ofstream out("order.out");
in >> n;
for (int i = 1; i <= n; ++i) {
bit[i] += 1;
if (i + lsb(i) <= n)
bit[i + lsb(i)] += bit[i];
}
logMax = (int)floor(log2(n));
int prev = 1;
for (int k = 1; k <= n; ++k) {
int remaining = n - k + 1;
int target = query(prev) + k % remaining;
if (target > remaining)
target -= remaining;
if (target == 0)
target = remaining;
prev = search(target);
out << prev << ' ';
update(prev, -1);
}
return 0;
}