Cod sursa(job #3318220)

Utilizator informatica1210Alexia Petre informatica1210 Data 27 octombrie 2025 15:59:17
Problema Curcubeu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
#include "bits/stdc++.h"
using namespace std;
ifstream f ("curcubeu.in");
ofstream g ("curcubeu.out");
int t[1000002],nr[1000002],u[1000002],a[1000002],b[1000002],c[1000002],v[1000002];
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)
{
    t[x]=fi(x);t[y]=fi(y);
    if (t[x]!=t[y])
    {
    if (nr[t[x]]>nr[t[y]])
    {
        nr[t[x]]+=nr[t[y]];
        t[t[y]]=t[t[x]];
        u[t[y]]=max (u[t[y]],u[t[x]]);
    }
    else
    {
        nr[t[y]]+=nr[t[x]];
        t[t[x]]=t[t[y]];
        u[t[x]]=max (u[t[x]],u[t[y]]);
    }
    }
}
int main ()
{
    int n,x,y,tt;
    f>>n>>a[1]>>b[1]>>c[1];
    for (x=2;x<n;x++)
    {
        a[x]=(a[x-1]*x)%n;
        b[x]=(b[x-1]*x)%n;
        c[x]=(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[x]==0)
             {
                 v[x]=c[x];
                 t[x]=x;nr[x]=1;u[x]=x;
                 if (v[x-1]!=0)
                 {
                     un(x-1,x);
                 }
                 if (v[x+1]!=0)
                 {
                     un (x,x+1);
                 }
             }
             else
             {
                 tt=fi(x);
                 y=u[tt];
             }
        }
    }
    for (x=1;x<n;x++)
        g<<v[x]<<'\n';
    f.close ();
    g.close ();
    return 0;
}