Cod sursa(job #3311183)

Utilizator pkseVlad Bondoc pkse Data 20 septembrie 2025 11:43:08
Problema Curcubeu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <bits/stdc++.h>
#define int long long 
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;
    }
};

signed 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());

    DSU dsu(n);

    n --;

    vector<int> ans(n);

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

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