Cod sursa(job #92184)

Utilizator filipbFilip Cristian Buruiana filipb Data 14 octombrie 2007 13:03:40
Problema Curcubeu Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#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;
}