Cod sursa(job #3267114)

Utilizator amcbnCiobanu Andrei Mihai amcbn Data 11 ianuarie 2025 09:46:31
Problema Curcubeu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin(".in");
ofstream fout(".out");

// Works with nodes in range [1, size]
struct union_find {
    vector<int> parent, rank;
    int size, components;
    union_find(int size = 0) {
        this->resize(size);
    }
    void resize(int size) {
        this->size = size;
        this->components = size;
        parent.resize(size + 1);
        for (int i = 1; i <= size; ++i) {
            parent[i] = i;
        }
        rank.assign(size + 1, 1);
    }
    int find(int x) {
        return parent[x] == x ? x : (parent[x] = find(parent[x]));
    }
    void merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return;
        }
        if (rank[x] < rank[y]) {
            swap(x, y);
        }
        parent[y] = x;
        rank[x] += rank[y];
        rank[y] = 0;
    }
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
};

const int nmax = 1e6;
int n, a, b, c;
struct Update {
    int l, r, color;
    Update() {}
    Update(int l, int r, int color) {
        if (l > r) {
            swap(l, r);
        }
        this->l = l;
        this->r = r;
        this->color = color;
    }
};
Update updates[nmax + 5];
int color[nmax + 5];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
    fin >> n >> a >> b >> c;
    updates[1] = Update(a, b, c);
    for (int i = 2; i < n; ++i) {
        a = 1ll * a * i % n;
        b = 1ll * b * i % n;
        c = 1ll * c * i % n;
        updates[i] = Update(a, b, c);
    }
    union_find dsu(n);
    // t[i] = urmatoarea pozitie necolorata
    for (int i = n - 1; i >= 1; --i) {
        int j = dsu.find(updates[i].l);
        while (j <= updates[i].r) {
            color[j] = updates[i].color;
            dsu.parent[j] = updates[i].r + 1;
            j = dsu.find(j + 1);
        }
    }
    for (int i = 1; i < n; ++i) {
        fout << color[i] << "\n";
    }
}