Cod sursa(job #3249479)

Utilizator AndreiDragosDavidDragos Andrei David AndreiDragosDavid Data 16 octombrie 2024 17:11:24
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#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;
}