Cod sursa(job #1460074)

Utilizator andreea_zahariaAndreea Zaharia andreea_zaharia Data 11 iulie 2015 15:55:25
Problema Curcubeu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <cstdio>

#define NMAX 1000000

int N, A, B, C;
int col[NMAX + 1];
int ant[NMAX + 1];
int vA[NMAX], vB[NMAX], vC[NMAX];

inline int finalAnt (int x) {
    if (ant[x] != x) {
        return ant[x] = finalAnt (ant[x]);
    }

    return x;
}

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

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

    for (int crt = 1; crt < N; crt++) {
        ant[crt] = crt;

        A = ((long long) A * crt) % N;
        B = ((long long) B * crt) % N;
        C = ((long long) C * crt) % N;

        vA[crt] = A;
        vB[crt] = B;
        vC[crt] = C;
    }

    for (int q = N - 1; q >= 1; q--) {
        if (vA[q] > vB[q]) {
            A = vB[q];
            B = vA[q];
        }
        else {
            A = vA[q];
            B = vB[q];
        }
        C = vC[q];

        int i;
        for (i = finalAnt (B); i >= A; i = finalAnt(i - 1)) {
            col[i] = C;
            ant[i] = A - 1;
        }
        ant[B] = i;
    }

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


    return 0;
}