Cod sursa(job #2087307)

Utilizator RaduGiucleaGiuclea Radu RaduGiuclea Data 13 decembrie 2017 12:28:41
Problema Curcubeu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <cstdio>
#include <algorithm>
using namespace std;
struct aa{int a;int b;int c;};
int tata[1000002],paint[1000002],interval[1000002];
aa v[1000002];
int fnd(int a)
{
    int c=a,c2;
    while(tata[a]!=0)
        a=tata[a];
    while(c!=a)
    {
        c2=tata[c];
        tata[c]=a;
        c=c2;
    }
    return a;
}
void color(int x)
{
    int a=v[x].a,b=v[x].b,c=v[x].c,i,t1,t2;
    for(i=a;i<=b;i++)
    {
        if(paint[i]==0)
            paint[i]=c,interval[i]=x;
        else
        {
            t1=fnd(x);
            t2=fnd(interval[i]);
            tata[t2]=t1;
            v[x].b=max(v[x].b,v[interval[i]].b);
            i=v[interval[i]].b;
        }
    }
}
int main()
{
    freopen("curcubeu.in","r",stdin);
    freopen("curcubeu.out","w",stdout);
    int n,a,b,c,i;
    scanf("%d%d%d%d",&n,&a,&b,&c);
    v[1].a=a;
    v[1].b=b;
    v[1].c=c;
    if(v[1].b<v[1].a)
            swap(v[1].b,v[1].a);
    for(i=2;i<=n-1;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;
        if(v[i].b<v[i].a)
            swap(v[i].b,v[i].a);
    }
    for(i=n-1;i>=1;i--)
        color(i);
    for(i=1;i<=n-1;i++)
        printf("%d\n",paint[i]);
    return 0;
}