Cod sursa(job #998115)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 15 septembrie 2013 19:52:46
Problema Curcubeu Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <fstream>

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");

    int i,copie;
    cin>>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';
    cin.close();
    cout.close();
    return 0;
}