Cod sursa(job #3323181)

Utilizator PudakPudak Nurberdiyev Pudak Data 17 noiembrie 2025 15:25:42
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.73 kb
#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;
}