Cod sursa(job #3304746)

Utilizator McMeatGhenea Radu Stefan McMeat Data 26 iulie 2025 18:46:07
Problema Curcubeu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fein("curcubeu.in");
ofstream g("curcubeu.out");
#define NMAX 1000010
#define pii pair<int,int>

int n, k, t[NMAX], rang[NMAX], a, b, c;

int get_root(int nod)
{
    int aux = nod;
    while(t[nod]!=nod)
    {
        nod = t[nod];
    }
    int r = nod;
    while(aux!=r)
    {
        nod = aux;
        aux = t[aux];
        t[nod]=r;
    }
    return r;
}

void join(int x, int y)
{
    int rx = get_root(x);
    int ry = get_root(y);

    if(ry==rx) return;
    if(rang[rx]<rang[ry])
    {
        t[rx]=ry;
        rang[ry]+=rang[rx];
    }
    else
    {
        // if(rang[rx]==rang[ry])
        //     rang[rx]++;
        t[ry]=rx;
        rang[rx]+=rang[ry];
    }
}

int main()
{
    fein>>n;
    vector<int> a(n+1), b(n+1), c(n+1), col(n+1, 0);
    fein>>a[1]>>b[1]>>c[1];
    if(a[1] > b[1]) swap(a[1], b[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;
        if(a[1] > b[1]) swap(a[1], b[1]);
    }
    for(int i=0;i<=n;i++)
        t[i]=i;
    for(int i=n-1;i>0;i--)
    {
        int r = get_root(a[i]);
        while(r<=b[i])
        {
            col[r]=c[i];
            t[r]=b[i]+1;
            r=get_root(r+1);
        }
    }
    for(int i=1;i<n;i++)
        g<<col[i]<<'\n';
    return 0;
}