Cod sursa(job #3191984)

Utilizator Manolea_Teodor_StefanManolea Teodor Stefan Manolea_Teodor_Stefan Data 11 ianuarie 2024 08:46:48
Problema Curcubeu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <bits/stdc++.h>
#define MAX_N 1000005

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

int n;
array<int, MAX_N> A,B,C,Culoare,T;

int getRoot(int node) {
    int _node = node;
    while (T[_node] !=  _node) {
        _node = T[_node];
    }
    while(node != _node) {
        const int aux = T[node];
        T[node] = _node;
        node = aux;
    }
    return _node;
}
void join(int nodeA, int nodeB) {
    int rootA = getRoot(nodeA);
    int rootB = getRoot(nodeB);
    if (rootA < rootB) {
        T[rootA] = rootB;
    } else {
        T[rootB] = rootA;
    }
}

int main() {
    fin >> n;
    fin >> A[1] >> B[1] >> C[1];
    Culoare[1] = 0;
    T[1] = 1;
    for (int i = 2; i < n; i++) {
        A[i] = (A[i-1] * i) % n;
        B[i] = (B[i-1] * i) % n;
        C[i] = (C[i-1] * i) % n;
        Culoare[i] = 0;
        T[i] = i;
    }


    for (int i = n - 1; i > 0; i--) {
        const int _left = min(A[i],B[i]);
        const int _right = max(A[i],B[i]);
        for (int k = getRoot(_left); k <= _right && k && k <= n; k = getRoot(k+1)) {
            if (Culoare[k]) {
                if (k-1) {
                    if (Culoare[k-1]) {
                        join(k, k-1);
                    }
                }
                if (k+1 <= n) {
                    if (Culoare[k+1]) {
                        join(k,k+1);
                    }
                }
            } else {
                Culoare[k] = C[i];
                T[i] =  _right + 1;
            }
        }
    }
    for (int i = 1; i < n; i++) {
        fout << Culoare[i] << '\n';
    };


    return 0;
}