Cod sursa(job #3364543)

Utilizator prodsevenStefan Albu prodseven Data 5 septembrie 2026 12:40:03
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream cin("order.in");
ofstream cout("order.out");

int n;

class FenwickTree {
    vector<int> tree;
    int size;
    void update_(int pos) {
        for (int i = pos ; i <= n ; i += i & -i) {
            tree[i] -= 1;
        }
    }
    int query_(int pos) {
        int ans = 0;
        for (int i = pos ; i > 0 ; i -= i & -i) {
            ans += tree[i];
        }
        return ans;
    }
public:
    FenwickTree(int size) {
        this->size = size;
        tree.assign(size + 2, 0);
        for (int i = 1 ; i <= size ; ++i) {
            tree[i] = i & -i;
        }
    }
    void update(int pos) {
        update_(pos);
    }
    int exact_sum_position(int sum) {
        int ans_idx = 0, current_sum = 0;
        for (int i = 1 << 30 ; i > 0 ; i >>= 1) {
            if (ans_idx + i <= n && current_sum + tree[ans_idx + i] < sum) {
                ans_idx += i;
                current_sum += tree[ans_idx];
            }
        }
        if (ans_idx + 1 > n || query_(ans_idx + 1) != sum) {
            return -1;
        }
        return ans_idx + 1;
    }
};

int main() {
    cin >> n;
    int r = 2;
    FenwickTree t(n);
    for (int i = 1 ; i <= n ; ++i) {
        int remaining = n - i + 1;
        r = ((r + i - 2) % remaining) + 1;
        int ans_idx = t.exact_sum_position(r);
        cout << ans_idx << " ";
        t.update(ans_idx);
    }
    return 0;
}