Pagini recente » Cod sursa (job #2139556) | Cod sursa (job #2804165) | Cod sursa (job #2759323) | Cod sursa (job #3265289) | Cod sursa (job #2646606)
// Oh damn, cann't you see I'm fine?
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
struct FenwickTree {
int n;
vector <int> t;
FenwickTree(int nn) {
n = nn;
t.resize(n + 1);
}
void update(int idx, int delta) {
while(idx <= n) {
t[idx] += delta;
idx += (idx & -idx);
}
}
int sum(int idx) {
int res = 0;
while(idx > 0) {
res += t[idx];
idx -= (idx & -idx);
}
return res;
}
// largest index such that sum[idx] < val (or last)
int firstIndexOfGE(int val) {
int step = (1 << 30);
int i = 0;
int now = 0;
while (step > 0) {
if (i + step <= n && now + t[i + step] < val) {
now += t[i + step];
i += step;
}
step /= 2;
}
return i;
}
void debug() {
for(int i = 1; i <= n; i++) {
cerr << sum(i) - sum(i - 1) << " ";
}
cerr << endl;
}
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
freopen("order.in", "r", stdin);
freopen("order.out", "w", stdout);
int n;
cin >> n;
FenwickTree ft(n);
for(int i=1; i<=n; i++) ft.update(i, 1);
int now = 1;
int all = n;
for(int i=1; i<=n; i++) {
int j = i % all;
if(j == 0) j = all;
int rem = ft.sum(n) - ft.sum(now);
if(rem < j) {
now = 0;
j -= rem;
}
int l = now, r = n, m;
while(r > l) {
m = (l + r) >> 1;
int v = ft.sum(m) - ft.sum(now);
if(v > j) r = m-1;
else if(v < j) l = m+1;
else r = m;
}
cout << r << " ";
ft.update(r, -1);
now = r;
all--;
}
return 0;
}