Cod sursa(job #3362467)

Utilizator RobertIon013Ion Robert Andrei RobertIon013 Data 9 august 2026 12:38:40
Problema Curcubeu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <bits/stdc++.h>

using namespace std;
int cnt,minpoz,maxpoz,n;
struct idk
{
    vector<int> parent;
    idk(int k)
    {
        parent.resize(k+5);
        for(int i=1;i<=k;i++)
        {
            parent[i]=i;
        }
    }
    int dsu(int nod)
    {
        if(parent[nod]==nod)
        {
            return nod;
        }
        return parent[nod]=dsu(parent[nod]);
    }
};
int a[1000001];
int b[1000001];
int c[1000001];
int main()
{
    freopen("curcubeu.in","r",stdin);
    freopen("curcubeu.out","w",stdout);
    cin>>n;
    cin>>a[1]>>b[1]>>c[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;
    }
    idk parinte(n);
    vector<int> rez(n+1);
    for(int i=n-1;i>=1;i--)
    {
        minpoz=min(a[i],b[i]);
        maxpoz=max(a[i],b[i]);
        cnt=parinte.dsu(minpoz);
        while(cnt<=maxpoz)
        {
            rez[cnt]=c[i];
            parinte.parent[cnt]=cnt+1;
            cnt=parinte.dsu(cnt);
        }
    }
    for(int i=1;i<n;i++)
    {
        cout<<rez[i]<<'\n';
    }

    return 0;
}