Cod sursa(job #3311178)

Utilizator pkseVlad Bondoc pkse Data 20 septembrie 2025 11:15:01
Problema Curcubeu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <bits/stdc++.h>
using namespace std;

struct DSU {
    int n;
    vector<int> a;

    DSU(int N) {
        N = n;
        a.resize(n);
        for(int i = 0; i < n; i ++) {
            a[i] = i;
        }
    }

    int leader(int x) {
        if(x == a[x])
            return x;
        return a[x] = leader(a[x]);
    }

    void merge(int x, int y) {
        x = leader(x);
        y = leader(y);
        a[x] = y;
    }
};

int main() {
    freopen("curcubeu.in", "r", stdin);
    freopen("curcubeu.out", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n; cin >> n;

    vector<int> a(n - 1), b(n - 1), c(n - 1);

    cin >> a[0] >> b[0] >> c[0];

    for(int i = 1; i < n - 1; i ++) {
        a[i] = (a[i - 1] * (i + 1)) % n;
        b[i] = (b[i - 1] * (i + 1)) % n;
        c[i] = (c[i - 1] * (i + 1)) % n;
    }

    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    reverse(c.begin(), c.end());

    n --;

    DSU dsu(n + 1);

    vector<int> ans(n);

    for(int i = 0; i < n; i ++) {
        a[i] --;
        for(int j = dsu.leader(a[i]); j < b[i]; j = dsu.leader(j)) {
            ans[i] = c[i];
            dsu.merge(j, j + 1);
        }
    }

    for(auto i : ans) {
        cout << i << '\n';
    }
}