Cod sursa(job #3191411)

Utilizator Cazacu2006RazvanRazvan Cazacu Cazacu2006Razvan Data 9 ianuarie 2024 17:47:06
Problema Curcubeu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <fstream>

using namespace std;
ifstream fin("curcubeu.in");
ofstream fout("curcubeu.out");
int n,x,y,z,tata[10000001],dr[10000001],cul[10000001];
struct numar
{
    int A,B,C;
}v[1000001];
int rad(int x)
{
    while(tata[x]>0)
    {
        x=tata[x];
    }
    return x;
}
void join(int i,int j)
{
    int x=rad(i);
    int y=rad(j);
    if(tata[x]>tata[y])
        swap(x,y);

        tata[x]+=tata[y];
        tata[y]=tata[x];
        dr[x]=max(dr[x],dr[y]);


}
int main()
{
    fin>>n>>v[1].A>>v[1].B>>v[1].C;
    for(int i=2;i<=n;i++)
    {
        v[i].A=(v[i-1].A*i)%n;
        v[i].B=(v[i-1].B*i)%n;
        v[i].C=(v[i-1].C*i)%n;
        tata[i-1]=-1;
        cul[i-1]=-1;
    }

    for(int i=n;i>=1;i--)
    {
        for(int j=min(v[i].A,v[i].B);j<=max(v[i].A,v[i].B);j++)
        {
           if(cul[j]==-1)
           {
               cul[j]=v[i].C;
               dr[j]=i;
               if(j>1 && cul[j-1]!=-1)
               {
                   join(j-1,j);
               }
               if(j+1<n && cul[j+1]!=-1)
               {
                   join(j,j+1);
               }
           }
           else
           {
               j=dr[rad(j)]+1;
           }
        }
    }
    for(int i=1;i<n;i++)
        fout<<cul[i]<<"\n";



    return 0;
}