Pagini recente » Cod sursa (job #2031378) | Cod sursa (job #2538480) | Cod sursa (job #2386433) | Cod sursa (job #440551) | Cod sursa (job #3191999)
#include <bits/stdc++.h>
#define MAX_N 1000010
using namespace std;
ifstream fin("curcubeu.in");
ofstream fout("curcubeu.out");
int n;
int A[MAX_N],B[MAX_N],C[MAX_N],Culoare[MAX_N],T[MAX_N];
int getRoot(int node) {
int _node = node;
if (node > n) {
return 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) {
return;
}
if (rootA < rootB) {
T[rootA] = rootB;
} else {
T[rootB] = rootA;
}
}
int main() {
fin >> n;
fin >> A[1] >> B[1] >> C[1];
A[1] %= n;
B[1] %= n;
C[1] %= n;
Culoare[1] = -1;
T[1] = 1;
for (int i = 2; i < MAX_N; i++) {
A[i] = (1ll*A[i-1] * i) % n;
B[i] = (1ll*B[i-1] * i) % n;
C[i] = (1ll*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[k] = _right + 1;
}
}
}
for (int i = 1; i < n; i++) {
if (Culoare[i] == -1) {
fout << 0 << '\n';
} else {
fout << Culoare[i] << '\n';
}
}
return 0;
}