Cod sursa(job #3311925)

Utilizator pkseVlad Bondoc pkse Data 24 septembrie 2025 22:08:43
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.53 kb
#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 << ' ';
    }
}