Cod sursa(job #1825446)

Utilizator SirStevensIonut Morosan SirStevens Data 9 decembrie 2016 10:22:22
Problema Curcubeu Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <bits/stdc++.h>

using namespace std;

FILE *in = freopen("curcubeu.in", "r" , stdin);
FILE *out = freopen("curcubeu.out", "w", stdout);

int t[1000005],l[1000005],casuta[1000005],a[1000000],b[1000000],c[1000000],n,copie;
bool pictat[1000005];

void init(int n){

    for(int i=1;i<=n;i++)
        t[i]=0,l[i]=1;
}

int minim(int a, int b)
{
    if(a>b)
        return b;
    return a;
}

int maxim(int a, int b)
{
    if(a>b)
        return a;
    return b;
}

int caut(int x)
{
    int rad = x;
    while(t[rad]!= 0)
        rad=t[rad];
    int tmp;
    while(t[x] != 0)
    {
        tmp = t[x];
        t[x] = rad;
        x = tmp;

    }
    return rad;
}

void reunion(int x, int y){

    x=caut(x);
    y=caut(y);
    if(x == y)
        return ;
    t[y]=x;
    l[x]+=l[y];

}

void rainbow(int x, int y, int cul){

    for(int i=x; i<=y ; i+=l[i]){

        if(!pictat[i]){

            casuta[i]=cul;
            pictat[i]=1;
            if(i >= 2)
                if(pictat[i-1])
                    reunion(i-1,i);

            if(i<n)
                if(pictat[i+1])
                    reunion(i,i+1);


        }
        i=caut(i);
    }

}

int main()
{
    scanf("%d %d %d %d", &n, &a[1], &b[1], &c[1]);
    copie=n--;
    init(n);
    for(int i=2;i<=n;i++)
        a[i]=(a[i-1]*i)%copie,b[i]=(b[i-1]*i)%copie,c[i]=(c[i-1]*i)%copie;
    for(int j=n;j>=1;j--)
    {
        rainbow(minim(a[j],b[j]),maxim(a[j],b[j]),c[j]);
    }
    for(int i=1;i<=n;i++)
        printf("%d\n", casuta[i]);
    return 0;
}