Pagini recente » Cod sursa (job #807107) | Cod sursa (job #1657262) | Cod sursa (job #2851834) | Cod sursa (job #1933277) | Cod sursa (job #3323181)
#include <bits/stdc++.h>
using namespace std;
struct Fenwick {
int n;
vector<int> bit; // 1-indexed
void init(int n_) {
n = n_; bit.assign(n+1, 0);
}
void add(int i, int v) {
for (; i <= n; i += i & -i)
bit[i] += v;
}
int sum(int i) const {
int s = 0;
for (; i > 0; i -= i & -i)
s += bit[i];
return s;
}
// smallest idx with prefix sum >= k (requires all values >= 0, k>=1)
int find_kth(int k) const {
int idx = 0;
int step = 1;
while ((step << 1) <= n) step <<= 1; // highest power of two <= n
for (; step; step >>= 1) {
int next = idx + step;
if (next <= n && bit[next] < k) {
k -= bit[next];
idx = next;
}
}
return idx + 1; // 1-indexed
}
};
int main() {
freopen("order.in", "r", stdin);
freopen("order.out", "w", stdout);
int n;
cin >> n;
Fenwick fw;
fw.init(n);
for (int i = 1; i <= n; ++i) fw.add(i, 1); // everyone alive
vector<int> out;
int alive = n;
long long pos = 2; // first eliminated is the 2nd child
for (int step = 1; step <= n; ++step) {
int idx = fw.find_kth((int)pos); // the actual index in [1..n]
out.push_back(idx);
fw.add(idx, -1); // eliminate
--alive;
if (alive > 0) {
// advance by step 'step' from the next position in the circle
pos = (pos + step) % alive;
if (pos == 0) pos = alive; // wrap to [1..alive]
//cout<<pos<<" ----"<<step<<endl;
}
}
for (int i = 0; i < n; ++i)
cout<<out[i]<<" ";
return 0;
}