Pagini recente » Cod sursa (job #3347137) | Cod sursa (job #2808298) | Cod sursa (job #111253) | Cod sursa (job #3130265) | Cod sursa (job #3311925)
#include <bits/stdc++.h>
using namespace std;
int lsb(int x) {
return x & (-x);
}
struct AIB {
vector<int> a;
int n;
AIB(int N) {
n = N;
a.resize(n);
}
void update(int p, int val) {
if(p > n)
return;
a[p - 1] += val;
update(p + lsb(p), val);
}
int pf(int p) {
if(p <= 0)
return 0;
return a[p - 1] + pf(p - lsb(p));
}
// void outfordebug() {
// for(int i = 1; i <= n; i ++) {
// cout << pf(i) - pf(i - 1) << ' ';
// }
// cout << '\n';
// }
int cb(int p, int val) {
// outfordebug();
int ipf = pf(p);
int st = p, dr = n, ans;
while(st <= dr) {
int mj = (st + dr) / 2;
int rez = pf(mj) - ipf;
if(rez >= val) {
ans = mj;
dr = mj - 1;
} else {
st = mj + 1;
}
}
if(ans > n / 2)
ans -= n / 2;
return ans;
}
};
int main() {
freopen("order.in", "r", stdin);
freopen("order.out", "w", stdout);
int n; cin >> n;
AIB aib(2 * n);
for(int i = 1; i <= 2 * n; i ++) {
aib.update(i, 1);
}
int skip = 1;
for(int i = 0, j = 1; i < n; skip ++, i ++) {
j = aib.cb(j, (skip % (n - i)) ? (skip % (n - i)) : (n - i));
aib.update(j, -1);
aib.update(j + n, -1);
cout << j << ' ';
}
}