Cod sursa(job #764243)

Utilizator cont_de_testeCont Teste cont_de_teste Data 4 iulie 2012 15:37:55
Problema Curcubeu Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
# include <algorithm>
# include <cstdio>
using namespace std;

const char *FIN = "curcubeu.in", *FOU = "curcubeu.out";
const int MAX = 1000005;

int N, A[MAX], B[MAX], C[MAX], V[MAX], sol[MAX], T[MAX];

inline int search (int X) {
    int rang;
    for (rang = X; T[rang] != rang; rang = T[rang]);
    for (int aux; T[X] != X;) {
        aux = T[X];
        T[X] = rang;
        X = aux;
    }
    return rang;
}

inline void unite (int X, int Y) {
    if (X < Y) T[X] = Y;
    else T[Y] = X;
}

inline void doit (int *A, int i) {
    A[i] = (1LL * A[i - 1] * i) % N;
}

int main (void) {
    fscanf (fopen (FIN, "r"), "%d %d %d %d", &N, A + 1, B + 1, C + 1);
    for (int i = 2; i < N; T[i] = i++) {
        doit (A, i), doit (B, i), doit (C, i);
        if (A[i] > B[i]) swap (A[i], B[i]);
    }
    T[1] = 1, T[N] = N;
    for (int i = N - 1; i; --i)
        for (A[i] = search (A[i]); A[i] <= B[i]; A[i] = search (A[i]))
            sol[A[i]] = C[i], unite (search (A[i]), search (A[i] + 1));
    freopen (FOU, "w", stdout);
    for (int i = 1; i < N; ++i)
        printf ("%d\n", sol[i]);
}