Cod sursa(job #561474)

Utilizator cosmyoPaunel Cosmin cosmyo Data 20 martie 2011 15:33:48
Problema Curcubeu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <cstdio>
const int N = 1000005;
int st[N], dr[N], n, a, b, c, C[N], t[N], cl[N];

int inline min(int a, int b) {
    return a < b ? a : b;
}

int inline max(int a, int b) {
    return a > b ? a : b;
}

int inline root(int x) {
    int r, y;
    for(r = x; r != t[r]; r = t[r]);

    for(;x != r; ) {
        y = t[x];
        t[x] = r;
        x = y;
    }

    return r;
}

inline void unite(int x, int y) {
    t[x] = y;
}

int main() {
    freopen("curcubeu.in", "r", stdin);
    freopen("curcubeu.out", "w", stdout);
    int i;
    scanf("%d %d %d %d", &n, &a, &b, &c);
    for(i = 1; i < n; ++i) {
        st[i] = min(a, b);
        dr[i] = max(a, b);
        C[i] = c;
        a = (a * (i + 1)) % n;
        b = (b * (i + 1)) % n;
        c = (c * (i + 1)) % n;
    }

    int nr = n - 1, rl, rd, j;

    for(i = 1; i <= n; ++i)
        t[i] = i;

    for(i = n - 1; i >= 1 && nr; --i) {
        rl = root(st[i]);
        if(rl == st[i])
            --rl;
        rd = root(dr[i]);

        for(j = rl + 1; j <= dr[i]; ++j)
            unite(j, rd),  cl[j] = C[i];

         nr -= dr[i] - rl;
    }

    for(i = 1; i <= n - 1; ++i)
        printf("%d\n", cl[i]);

    return 0;
}