Pagini recente » Cod sursa (job #2809131) | Cod sursa (job #2345669) | Cod sursa (job #164264) | Cod sursa (job #2498775) | Cod sursa (job #3191987)
#include <bits/stdc++.h>
#define MAX_N 1000005
using namespace std;
ifstream fin("curcubeu.in");
ofstream fout("curcubeu.out");
int n;
array<int, MAX_N> A,B,C,Culoare,T;
int getRoot(int node) {
int _node = node;
while (T[_node] != _node) {
_node = T[_node];
}
while(node != _node) {
const int aux = T[node];
T[node] = _node;
node = aux;
}
return _node;
}
void join(int nodeA, int nodeB) {
int rootA = getRoot(nodeA);
int rootB = getRoot(nodeB);
if (rootA < rootB) {
T[rootA] = rootB;
} else {
T[rootB] = rootA;
}
}
int main() {
fin >> n;
fin >> A[1] >> B[1] >> C[1];
Culoare[1] = -1;
T[1] = 1;
for (int i = 2; i < n; i++) {
A[i] = (A[i-1] * i) % n;
B[i] = (B[i-1] * i) % n;
C[i] = (C[i-1] * i) % n;
Culoare[i] = -1;
T[i] = i;
}
for (int i = n - 1; i > 0; i--) {
const int _left = min(A[i],B[i]);
const int _right = max(A[i],B[i]);
for (int k = getRoot(_left); k <= _right && k && k < n; k = getRoot(k+1)) {
if (Culoare[k] != -1) {
if (k-1) {
if (Culoare[k-1] != -1) {
join(k, k-1);
}
}
if (k+1 <= n) {
if (Culoare[k+1] != -1) {
join(k,k+1);
}
}
} else {
Culoare[k] = C[i];
T[i] = _right + 1;
}
}
}
for (int i = 1; i < n; i++) {
if (Culoare[i] == -1) {
fout << 0 << '\n';
} else {
fout << Culoare[i] << '\n';
}
}
return 0;
}