Cod sursa(job #998117)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 15 septembrie 2013 20:02:54
Problema Curcubeu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <cstdio>

using namespace std;

int t[1000005],n;
int lung[1000005];

inline void init(int n)
{
    int i;
    for(i=1;i<=n;i++)
        t[i]=0,lung[i]=1;
}

int gaseste(int a)
{
    int r=a;
    while(t[r])
        r=t[r];
    int x,y;
    x=a;
    while(x!=r)
    {
        y=t[x];
        t[x]=r;
        x=y;
    }
    return r;
}

void uneste(int a,int b)
{
    a=gaseste(a);
    b=gaseste(b);
    if(a==b)
        return;
    t[b]=a;
    lung[a]+=lung[b];
}

bool painted[1000005];
int vect[1000005];

void rainbow(int x,int y,int cul)
{
   int i;
   for(i=x;i<=y;i+=lung[i])
   {
       if(!painted[i])
       {
          vect[i]=cul;
          painted[i]=1;
          if(i>=2)
             if(painted[i-1])
                uneste(i-1,i);
          if(i<n)
             if(painted[i+1])
                uneste(i,i+1);
       }
       i=gaseste(i);
   }
}

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

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

int a[1000005],b[1000005],c[1000005];

int main()
{
   // ifstream cin("curcubeu.in");
   // ofstream cout("curcubeu.out");
    freopen("curcubeu.in","r",stdin);
    freopen("curcubeu.out","w",stdout);


    int i,copie;
   // cin>>n>>a[1]>>b[1]>>c[1];
   scanf("%d%d%d%d",&n,&a[1],&b[1],&c[1]);
    copie=n--;
    init(n);
    for(i=2;i<=n;i++)
       a[i]=(((long long int)i*a[i-1])%copie),b[i]=(((long long int)i*b[i-1])%copie),c[i]=(((long long int)i*c[i-1])%copie);
    for(i=n;i>=1;i--)
    {
        //cout<<minim(a[i],b[i])<<' '<<maxim(a[i],b[i])<<' '<<c[i]<<endl;
        rainbow(minim(a[i],b[i]),maxim(a[i],b[i]),c[i]);
    }
    for(i=1;i<=n;i++)
        //cout<<vect[i]<<'\n';
        printf("%d\n",vect[i]);
    //cin.close();
    //cout.close();
    return 0;
}