Cod sursa(job #3191997)

Utilizator Manolea_Teodor_StefanManolea Teodor Stefan Manolea_Teodor_Stefan Data 11 ianuarie 2024 09:52:22
Problema Curcubeu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <bits/stdc++.h>
#define MAX_N 1000010

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

int n;
int A[MAX_N],B[MAX_N],C[MAX_N],Culoare[MAX_N],T[MAX_N];

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

int main() {
    fin >> n;
    fin >> A[1] >> B[1] >> C[1];
    A[1] %= n;
    B[1] %= n;
    C[1] %= n;
    Culoare[1] = -1;
    T[1] = 1;
    for (int i = 2; i < MAX_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;
        Culoare[i] = -1;
        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] != -1) {
                if (k-1) {
                    if (Culoare[k-1] != -1) {
                        join(k, k-1);
                    }
                }
                if (k+1 < n) {
                    if (Culoare[k+1] != -1) {
                        join(k,k+1);
                    }
                }
            } else {
                Culoare[k] = C[i];
                T[k] =  _right + 1;
            }
        }
    }
    for (int i = 1; i < n; i++) {
        if (Culoare[i] == -1) {
            fout << 0 << '\n';
        } else {
            fout << Culoare[i] << '\n';
        }
    }


    return 0;
}