Pagini recente » Cod sursa (job #2629673) | Cod sursa (job #284203) | Cod sursa (job #520581) | Cod sursa (job #91024) | Cod sursa (job #92184)
Cod sursa(job #92184)
#include <stdio.h>
#define maxim(a, b) ((a > b) ? a : b)
#define ll long long
#define NMax 1000005
int N, A[NMax], B[NMax], C[NMax], color[NMax];
int tata[NMax], rang[NMax], nxt[NMax];
int find_multime(int x)
{
if (x != tata[x])
tata[x] = find_multime(tata[x]);
return tata[x];
}
void uneste(int x, int y)
{
if (rang[x] < rang[y])
tata[x] = y, nxt[y] = maxim(nxt[x], nxt[y]);
else
{
tata[y] = x;
rang[x] += (rang[x] == rang[y]);
nxt[x] = maxim(nxt[x], nxt[y]);
}
}
int next(int x)
{
int i, j;
j = -1;
while (color[x])
{
i = find_multime(x);
if (j != -1)
uneste(i, j);
x = nxt[i];
j = i;
}
return x;
}
int main(void)
{
int i, j;
freopen("curcubeu.in", "r", stdin);
freopen("curcubeu.out", "w", stdout);
scanf("%d %d %d %d", &N, &A[1], &B[1], &C[1]);
for (i = 2; i < N; i++)
A[i] = ((ll)A[i-1] * i) % N,
B[i] = ((ll)B[i-1] * i) % N,
C[i] = ((ll)C[i-1] * i) % N;
for (i = 1; i < N; i++)
if (A[i] > B[i])
j = A[i], A[i] = B[i], B[i] = j;
for (i = 1; i <= N; i++)
nxt[i] = i, tata[i] = i, rang[i] = 1;
for (i = N-1; i; i--)
for (j = next(A[i]); j <= B[i]; j = next(j))
color[j] = C[i], nxt[j] = j+1;
for (i = 1; i < N; i++)
printf("%d\n", color[i]);
return 0;
}