Pagini recente » Cod sursa (job #1865) | Cod sursa (job #1378594) | Cod sursa (job #1919435) | Cod sursa (job #67705) | Cod sursa (job #2942035)
#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
#define stinl static inline
constexpr int MAX_N = 30005;
stinl void wrap(int& i, int N) {
i %= N;
if (i == 0) i = N;
}
namespace BIT {
int tree[MAX_N], N;
stinl void add(int i, int x) {
for (; i <= N; i += i & (-i))
tree[i] += x;
}
stinl int prefix(int i) {
int sum = 0;
for (; i > 0; i -= i & (-i))
sum += tree[i];
return sum;
}
stinl int segment(int i1, int i2) {
int cnt = (i2 - 1) / N;
wrap(i2, N);
return cnt * prefix(N) - prefix(i1 - 1) + prefix(i2);
}
stinl void init(int N) {
BIT::N = N;
for (int i = 1; i <= N; i++)
add(i, 1);
}
}
int N, i, pos, low, high, mid, sol, sum;
int main() {
fin >> N;
BIT::init(N);
pos = 1;
for (i = 1; i <= N; i++) {
low = pos + 1, high = pos + 1, sol = -1;
while (BIT::segment(pos + 1, high) <= i)
high *= 2;
while (low <= high) {
mid = (low + high) / 2;
sum = BIT::segment(pos + 1, mid);
if (sum >= i) {
sol = mid;
high = mid - 1;
}
else low = mid + 1;
}
pos = sol;
wrap(pos, N);
BIT::add(pos, -1);
fout << pos << ' ';
}
fin.close();
fout.close();
return 0;
}