Cod sursa(job #3165126)

Utilizator diana_dd03Dorneanu Diana diana_dd03 Data 5 noiembrie 2023 14:57:35
Problema Curcubeu Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <bits/stdc++.h>
using namespace std;

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

int N, a, b, c;
vector<int>A;
vector<int>B;
vector<int>C;
vector<int>h;
vector<int>t;

int FindR(int x){
    int root=x;
    while(t[root]!=root)
        root=t[root];

    while(x!=t[x]){
        int copie=t[x];
        t[x]=root;
        x=copie;
    }
    return root;
}

void Union(int rx, int ry){
    t[rx]=t[ry];
}

int main(){
    fin>>N;
    fin>>a>>b>>c;
    h.assign(N, 0);
    t.assign(N, 0);
    A.assign(N, 0);
    B.assign(N, 0);
    C.assign(N, 0);
    A[1]=a;
    B[1]=b;
    C[1]=c;
    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;
        t[i]=i;
    }
    for(int i=N-1;i>=1;i--){
        int r=FindR(min(A[i], B[i]));
        while(r<=max(A[i], B[i])){
            if(h[r]==0){
                h[r]=C[i];
                if(r!=max(A[i], B[i]))
                    Union(r, max(A[i], B[i]));
            }
            r=FindR(++r);
        }
    }
    for(int i=1;i<N;i++)
        fout<<h[i]<<'\n';
    return 0;
}