Cod sursa(job #3318230)

Utilizator informatica1210Alexia Petre informatica1210 Data 27 octombrie 2025 16:28:49
Problema Curcubeu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.54 kb
#include "bits/stdc++.h"
using namespace std;
ifstream f ("curcubeu.in");
ofstream g ("curcubeu.out");
int t[1000005],nr[1000005],u[1000005],a[1000005],b[1000005],c[1000005],v[1000005];
int fi (int x)
{
    if (t[x]==x) return x;
    else
    {
        t[x]=fi(t[x]);
        return t[x];
    }
}
void un (int x,int y)
{
    int radacina1,radacina2;
    radacina1=fi(x);radacina2=fi(y);
    if (radacina1!=radacina2)
    {
        if (nr[radacina1]>nr[radacina2]) ;
        else swap (radacina1,radacina2);
            nr[radacina1]+=nr[radacina2];
            u[radacina1]=max (u[radacina2],u[radacina1]);
            t[radacina2]=radacina1;
    }
}
int main ()
{
    int n,x,y,tt;
    f>>n>>a[1]>>b[1]>>c[1];
    for (x=2;x<n;x++)
    {
        a[x]=(1LL*a[x-1]*x)%n;
        b[x]=(1LL*b[x-1]*x)%n;
        c[x]=(1LL*c[x-1]*x)%n;
    }
    for (x=n-1;x>=1;x--)
    {
        for (y=min(a[x],b[x]);y<=max(a[x],b[x]);y++)
        {
             if (v[y]==0)
             {
                 v[y]=c[x];
                 t[y]=y;nr[y]=1;u[y]=y;
                 if (v[y-1]!=0)
                 {
                     un(y-1,y);
                 }
                 if (v[y+1]!=0)
                 {
                     un (y,y+1);
                     y=u[fi(y)];
                 }
             }
             else
             {
                 tt=fi(y);
                 y=u[tt];
             }
        }
    }
    for (x=1;x<n;x++)
        g<<v[x]<<'\n';
    f.close ();
    g.close ();
    return 0;
}