Cod sursa(job #3350562)

Utilizator eric_dragosDragos Eric eric_dragos Data 9 aprilie 2026 16:55:02
Problema Curcubeu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("curcubeu.in");
ofstream fout("curcubeu.out");
#define ll long long
struct DSU{
    vector<int> root;
    DSU(ll n){
        root.resize(n+1);
        for(int i = 1; i<=n; i++) root[i] = i;
    }
int find(int x){
    if(root[x] != x) root[x] = find(root[x]);
    return root[x];
}
};

int main(){
    long long n, A, B, C;
    fin >> n >> A >> B >> C;
    vector<ll> va(n, 0), vb(n, 0), vc(n, 0), cul(n, 0);
    DSU dsu(n);
    va[1] = A;
    vb[1] = B;
    vc[1] = C;
    for(int i = 2; i<n; i++){
        va[i] = (va[i-1]*i)%n;
        vb[i] = (vb[i-1]*i)%n;
        vc[i] = (vc[i-1]*i)%n;
    }
    vector<ll> ans(n, 0);
    for(int i = n-1; i>=1; i--){
        ll l = min(va[i], vb[i]), r = max(va[i], vb[i]);
        if(l == 0) l=1;

        ll pos = dsu.find(l);
        while(pos <= r){
            ans[pos] = vc[i];
            dsu.root[pos] = pos+1;
            pos = dsu.find(pos+1);
        }
    }
    for(int i = 1; i<n; i++) fout << ans[i] << '\n';

    return 0;
}