Pagini recente » Cod sursa (job #2135745) | Cod sursa (job #1794696) | Cod sursa (job #1955519) | Cod sursa (job #1165819) | Cod sursa (job #3267114)
#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";
}
}