Pagini recente » Cod sursa (job #1916058) | Cod sursa (job #2471123) | Cod sursa (job #474556) | Cod sursa (job #2104071) | Cod sursa (job #1742649)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("curcubeu.in");
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() {
freopen("curcubeu.out", "w", stdout);
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++)
printf("%d\n",color[i]);
return 0;
}