Cod sursa(job #87444)

Utilizator ScrazyRobert Szasz Scrazy Data 27 septembrie 2007 13:35:07
Problema Curcubeu Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <stdio.h>
#define NMAX 1000010

long p[NMAX];
int rang[NMAX];
long next[NMAX];
long m[NMAX];
long a[NMAX],b[NMAX],c[NMAX];

long n, s;
long min, max;

inline long minn(long a, long b)
{
    return a < b ? a : b;
}

inline long maxx(long a, long b)
{
    return a > b ? a : b;
} 

long HalmaztKeres(long x)
{
    if (x != p[x]) p[x]=HalmaztKeres(p[x]);
    return p[x];
}

void HalmaztKeszit(long x)
{
    p[x]=x;
    rang[x]=0;
}

void Osszekapcsol(long x, long y)
{
    if (rang[x]>rang[y]) 
    {
	p[y]=x;
	if (next[x]<next[y]) next[x]=next[y];
    }
    else 
    {
	p[x]=y;
	if (next[y]<next[x]) next[y]=next[x];
    }
    if (rang[x]==rang[y] && x != y) ++rang[y];
}

void Egyesit(long x, long y)
{
    Osszekapcsol(HalmaztKeres(x),HalmaztKeres(y));
}

int main()
{
    freopen("curcubeu.in","r",stdin);
    freopen("curcubeu.out","w",stdout);

    long i, j;

    scanf("%ld %ld %ld %ld", &n, &a[1], &b[1], &c[1]);

    for (i=2; i<=n-1; ++i)
    {
	a[i]=(a[i-1]*i)%n;
	b[i]=(b[i-1]*i)%n;
	c[i]=(c[i-1]*i)%n;
    }

    for (i=1; i<=n-1; ++i)
    {
	HalmaztKeszit(i);
	next[i]=i;
    }

    min=minn(a[n-1],b[n-1]);
    max=maxx(a[n-1],b[n-1]);

    for (i=min; i<=max; ++i) 
    {
	Egyesit(min,i);
	m[i]=c[n-1];
    }

    for (i=n-2; i>=1; --i)
    { 
	min=minn(a[i],b[i]);
	max=maxx(a[i],b[i]);

	for (j=min; j<=max; ++j)
	{
	    if (m[j]) 
	    {
		s=HalmaztKeres(j);
		j=next[s];
	    }
	    else
	    {
		m[j]=c[i];
		if (m[j-1])
		{
		    s=HalmaztKeres(j-1);
		    Egyesit(s,j);
		}
		if (m[j+1])
		{
		    s=HalmaztKeres(j+1);
		    Egyesit(s,j);
		}
	    }
	}
    }

    for (i=1; i<=n-1; ++i)
	printf("%ld\n", m[i]);

    fclose(stdin);
    fclose(stdout);

    return 0;

}