Cod sursa(job #2193092)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 8 aprilie 2018 18:36:49
Problema Curcubeu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <fstream>

#define MAX 1000005
using namespace std;

ifstream fin("curcubeu.in");
ofstream fout("curcubeu.out");

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


void swap(int &A, int &B){
    A ^= B;
    B ^= A;
    A ^= B;
}

int main()
{
    fin >> 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]);
    }

    for(int i = n - 1; i >= 1; --i){
        int 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)
        fout << culoare[i] << '\n';
    return 0;
}