Cod sursa(job #3191507)

Utilizator Cazacu2006RazvanRazvan Cazacu Cazacu2006Razvan Data 9 ianuarie 2024 20:27:18
Problema Curcubeu Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <fstream>

using namespace std;
ifstream fin("curcubeu.in");
ofstream fout("curcubeu.out");
int n,x,y,z,tata[1000001],dr[1000001],cul[1000001];
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(x==y)
        return;
    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-1;i++)
    {

        v[i].A=(1ll*v[i-1].A*i)%n;
        v[i].B=(1ll*v[i-1].B*i)%n;
        v[i].C=(1ll*v[i-1].C*i)%n;

    }
    for(int i=1;i<=n-1;i++)
    {
        tata[i]=-1;
        cul[i]=-1;
    }

    for(int i=n-1;i>=1;i--)
    {
        int st=min(v[i].A,v[i].B);
        int dr2=max(v[i].A,v[i].B);
       // fout<<min(1,min(v[i].A,v[i].B))<<" "<<max(v[i].A,v[i].B)<<" "<<v[i].C<<"\n";
        for(int j=st;j<=dr2;j++)
        {
           //fout<<j<<" ";
           if(cul[j]==-1)
           {

               cul[j]=v[i].C;
               dr[j]=j;
               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)];
           }
        }
    }
    int ok=1;
    for(int i=1;i<n;i++)
    {
        if(cul[i]==-1)
            ok=0;
    }
    if(ok==0)
    {
        fout<<0;
        return 0;
    }
    for(int i=1;i<n;i++)
        fout<<cul[i]<<"\n";



    return 0;
}