Pagini recente » Cod sursa (job #2963461) | Cod sursa (job #3181969) | Cod sursa (job #3162599) | Cod sursa (job #3165335) | Cod sursa (job #3249479)
#include <bits/stdc++.h>
using namespace std;
class BIT {
private:
vector<int> tree;
int n;
public:
BIT(int size) : n(size) {
tree.resize(n + 1, 0);
}
void update(int pos, int val) {
for (int i = pos; i <= n; i += i & -i)
tree[i] += val;
}
int query(int pos) const {
int result = 0;
for (int i = pos; i > 0; i -= i & -i)
result += tree[i];
return result;
}
int find_position(int sum) const {
int left = 1, right = n;
while (left < right) {
int mid = (left + right) / 2;
if (query(mid) >= sum)
right = mid;
else
left = mid + 1;
}
return left;
}
};
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
freopen("order.in", "r", stdin);
freopen("order.out", "w", stdout);
#endif
cin.tie(0)->sync_with_stdio(0);
int n; cin >> n;
BIT bit(n);
for (int i=1; i<=n; ++i)
bit.update(i, 1);
int pos=2;
for(int i=1; i<=n; ++i){
pos = (pos+i-1) % (n-i+1);
if (pos==0) pos = n-i+1;
int target_position = bit.find_position(pos);
cout << target_position << " ";
bit.update(target_position, -1);
}
return 0;
}