Cod sursa(job #2087666)

Utilizator RaduGiucleaGiuclea Radu RaduGiuclea Data 13 decembrie 2017 22:20:18
Problema Curcubeu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <cstdio>
#include <algorithm>
using namespace std;
struct aa{int a;int b;int c;};
int tata[1000002],paint[1000002];
aa v[1000002];
int fnd(int a)
{
    int c=a,c2;
    while(tata[a]!=a)
        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,t;
    for(i=a;i<=b;i++)
    {
        if(paint[i]==-1)
            paint[i]=c,tata[i]=b+1;
        else
        {
            t=fnd(i);
            i=t;
        }
    }
}
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);
    for(i=1;i<=n;i++)
        paint[i]=-1,tata[i]=i;
    v[1].a=a;
    v[1].b=b;
    v[1].c=c;
    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;
    }
    for(i=1;i<=n;i++)
        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++)
        if(paint[i]!=-1)
            printf("%d\n",paint[i]);
        else printf("0\n");
    return 0;
}