Cod sursa(job #2193096)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 8 aprilie 2018 18:40:11
Problema Curcubeu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <cstdio>

#define MAX 1000005

int n, Arbore[MAX], Rank[MAX], a[MAX], b[MAX], c[MAX], culoare[MAX];

/// Union find -Start
int findR(int val){
    int r = val, y;
    while(Arbore[r] != r)
        r = Arbore[r];

    ///compresia caii
    while(Arbore[val] != val){
        y = Arbore[val];
        Arbore[val] = r;
        val = y;
    }

    return r;
}

void Unite(int Rx, int Ry){
    if(Rank[Rx] > Rank[Ry])
        Arbore[Rx] = Ry;
    else Arbore[Ry] = Rx;

    if(Rank[Rx] == Rank[Ry])
        Rank[Ry] ++;
}
/// Finish

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

    scanf("%d%d%d%d", &n  , &a[1] , &b[1] , &c[1]);
    for(int i = 0; i < n; ++i){
        Arbore[i] = i;
        Rank[i] = 1;
    }

    if(a[1] > b[1])
        swap(a[1], b[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;

        if(a[i] > b[i])
            swap(a[i], b[i]);
    }

    int j;
    for(int i = n - 1; i >= 1; --i){
        j = findR(a[i]);
        while(j <= b[i] && j){
            if(culoare[j] == 0){
                culoare[j] = c[i];
                Unite(j, b[i]);
            }
            j = findR(++j);
        }
    }

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