Cod sursa(job #234613)

Utilizator Mishu91Andrei Misarca Mishu91 Data 21 decembrie 2008 12:47:51
Problema Curcubeu Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <cstdio>

#define MAX_N 1000005
//#define MAX_N 105

int N;
int A[MAX_N], B[MAX_N], C[MAX_N], Next[MAX_N], Sol[MAX_N];

void citire()
{
    scanf("%d %d %d %d",&N, A+1, B+1, C+1);

    for(int i = 2; i < 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;
    }

    for(int i = 1; i < N; ++i)
    {
        Next[i] = i + 1;
        if(A[i] > B[i])
        {
            A[i] ^= B[i];
            B[i] ^= A[i];
            A[i] ^= B[i];
        }
    }
}

void comprima(int x)
{
    int R;
    for(R = x; (Next[R] != 0) && (Next[R] != R+1);)
        R = Next[R];

    while((Next[x] != x+1) && (Next[x] != 0))
    {
        int aux = Next[x];
        Next[x] = R;
        x = aux;
    }
}

void solve()
{
    for(int i = N-1; i; --i)
    {
        int j = A[i];
        while(j <= B[i])
        {
            if(Sol[j] == 0)
                Sol[j] = C[i];
            int aux = Next[j];
            Next[j] = B[i] + 1;
            comprima(j);
            j = aux;
        }
    }

    for(int i = 1; i < N; ++i)
        printf("%d\n", Sol[i]);
}

int main()
{
    freopen("curcubeu.in","rt",stdin);
    freopen("curcubeu.out","wt",stdout);

    citire();
    solve();
}