Cod sursa(job #2006348)

Utilizator cipri321Marin Ciprian cipri321 Data 29 iulie 2017 15:22:50
Problema Curcubeu Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream>
#define DIM 1000001
using namespace std;
ifstream fi("curcubeu.in");
ofstream fo("curcubeu.out");
int n,A[DIM],B[DIM],C[DIM],CUL[DIM],D[DIM],P[DIM];
int radacina(int a)
{
    if(P[a]==0)
        return a;
    P[a]=radacina(P[a]);
    return P[a];
}
void reuneste(int a,int b)
{
    int ra=radacina(a),rb=radacina(b);
    if(ra!=rb)
    {
        D[ra]+=D[rb];
        P[rb]=ra;
    }
}
void smecherie(int st,int dr,int c)
{
    for(int i=st;i<=dr;i+=D[i])
    {
        if(CUL[i]==-1)
        {
            CUL[i]=c;
            if(i>1 && CUL[i-1]!=-1)
                reuneste(i-1,i);
            if(i<n && CUL[i+1]!=-1)
                reuneste(i,i+1);
        }
        i=radacina(i);
    }
}
int main()
{
    fi>>n>>A[1]>>B[1]>>C[1];
    for(int i=1;i<=n-1;i++)
        D[i]=1,CUL[i]=-1;
    for(int i=2;i<=n-1;i++)
    {
        A[i]=(1LL*A[i-1]*i)%n;
        C[i]=(1LL*C[i-1]*i)%n;
        B[i]=(1LL*B[i-1]*i)%n;
    }
    for(int i=n-1;i>=1;i--)
        smecherie(min(A[i],B[i]),max(A[i],B[i]),C[i]);
    for(int i=1;i<n;i++)
        fo<<CUL[i]<<"\n";
    fi.close();
    fo.close();
    return 0;
}