Cod sursa(job #1559840)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 31 decembrie 2015 17:15:51
Problema Curcubeu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1000000;
const int NIL = -1;

int st[MAX_N - 1];
int fn[MAX_N - 1];
int color[MAX_N - 1];
int jump[MAX_N - 1];
int v[MAX_N - 1];

int main()
{
    freopen("curcubeu.in", "r", stdin);
    freopen("curcubeu.out", "w", stdout);
    int N, A, B, C;

    scanf("%d%d%d%d", &N, &A, &B, &C);
    fclose(stdin);

    for ( register int i = 0; i < N - 1; ++i )
        jump[i] = NIL;

    for ( register int i = 2; i <= N; ++i )
    {
        if ( A > B )
            swap( A, B );

        st[i - 2] = A - 1;
        fn[i - 2] = B - 1;
        color[i - 2] = C;

        A = (1ULL * A * i) % N;
        B = (1ULL * B * i) % N;
        C = (1ULL * C * i) % N;
    }

    for ( register int i = N - 2; i >= 0; --i )
    {
        int j = st[i];

        while ( j <= fn[i] )
        {
            while ( jump[j] != NIL && j <= fn[i] )
                j = jump[j];

            if ( j <= fn[i] )
            {
                jump[j] = fn[i] + 1;
                v[j] = color[i];
            }

            j++;
        }
    }

    for ( register int i = 0; i < N - 1; ++i )
        printf("%d\n", v[i]);

    fclose(stdout);
    return 0;
}