Pagini recente » Cod sursa (job #1070223) | Cod sursa (job #1830843) | Cod sursa (job #2147678) | Cod sursa (job #1892444) | Cod sursa (job #1742644)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("curcubeu.in");
ofstream cout("curcubeu.out");
const int MAXN = 1000000;
int a[1 + MAXN], b[1 + MAXN], c[1 + MAXN];
int limit[1 + MAXN], h[1 + MAXN], dad[1 + MAXN], color[1 + MAXN];
int FindDad(int node) {
int current = node;
while (node != dad[node])
node = dad[node];
while (current != node) {
int temp = dad[current];
dad[current] = node;
current = temp;
}
return node;
}
void Join(int a, int b) {
if (h[a] > h[b]) {
dad[b] = a;
limit[a] = max(limit[a], limit[b]);
}
else {
dad[a] = b;
limit[b] = max(limit[a], limit[b]);
}
if (h[a] == h[b])
h[b]++;
}
int main() {
int n;
cin >> n >> a[1] >> b[1] >> c[1];
for (int i = 2; i <= n - 1; i++) {
a[i] = (1LL * i * a[i - 1]) % n;
b[i] = (1LL * i * b[i - 1]) % n;
c[i] = (1LL * i * c[i - 1]) % n;
}
for (int i = n - 1; i >= 1; i--) {
int left = min(a[i], b[i]);
int right = max(a[i], b[i]);
for (int j = left; j <= right; j++)
if (dad[j] == 0) {
dad[j] = j;
limit[j] = j;
if (dad[j - 1] != 0)
Join(FindDad(j), FindDad(j - 1));
color[j] = c[i];
}
else {
if (dad[j - 1] != 0)
Join(FindDad(j), FindDad(j - 1));
j = limit[FindDad(j)];
}
}
for (int i = 1; i <= n - 1; i++)
cout << color[i] << "\n";
return 0;
}