Cod sursa(job #1736827)

Utilizator Bodo171Bogdan Pop Bodo171 Data 2 august 2016 18:23:02
Problema Curcubeu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <iostream>
#include<fstream>
using namespace std;
const int nmax=1000005;
int r[nmax],rg[nmax],tt[nmax],y,aux,n,i,st,dr,j,col[nmax];
long long a[nmax],b[nmax],c[nmax];
int finds(int x)
{
    y=x;
    while(x!=tt[x])
        x=tt[x];
    while(y!=x)
    {
        aux=tt[y];
        tt[y]=x;
        y=aux;
    }
    return x;
}
void unite(int a,int b)
{
    if(rg[a]>rg[b]) {tt[b]=a;r[a]=max(r[a],r[b]);}
    else {tt[a]=b;r[b]=max(r[a],r[b]);}
    if(rg[a]==rg[b]) rg[b]++;
}
int main()
{
    ifstream f("curcubeu.in");
    ofstream g("curcubeu.out");
    f>>n>>a[1]>>b[1]>>c[1];
    for(i=2;i<=n-1;i++)
    {
        a[i]=i*a[i-1]%n;
        b[i]=i*b[i-1]%n;
        c[i]=i*c[i-1]%n;
    }
    for(i=n-1;i>=1;i--)
    {
        st=min(a[i],b[i]);
        dr=max(a[i],b[i]);
        for(j=st;j<=dr;j++)
        {
            if(tt[j]==0)
            {
                tt[j]=j;
                r[j]=j;
                if(tt[j-1]!=0) unite(j,j-1);
                col[j]=c[i];
            }else
            {
                if(tt[j-1]!=0) unite(j,j-1);
                j=r[finds(j)];
            }
        }
    }
    for(i=1;i<=n-1;i++)
        g<<col[i]<<'\n';
    return 0;
}