Cod sursa(job #535281)

Utilizator Alexa_ioana_14Antoche Ioana Alexandra Alexa_ioana_14 Data 16 februarie 2011 22:42:40
Problema Curcubeu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include<cstdio>
#define LL long long
#define NM 1000001
#define maxim(a,b) ((a>b)?a:b)
#define minim(a,b) ((a<b)?a:b)
LL a[NM],b[NM],c[NM];
int N,cul[NM],maxx,minn,gr[NM];
inline void mod(LL &x)
{
	if (x>=N)
		x%=N;
}
int find(int x)
{
	int i=x,j;
	for (; i!=gr[i]; i=gr[i]);
	while (x!=i)
	{
		j=gr[x];
		gr[x]=gr[i];
		x=j;
	}
}
inline void unesc(int x, int y)
{
	x=find(x);
	y=find(y);
	gr[x]=y;

}
inline void color()
{
	int num=0;
	for (int i=N-1; i&&num<N-1; --i)
	{
		minn=minim(a[i],b[i]);
		maxx=maxim(a[i],b[i]);
		
		minn=find(minn);
		while (minn<=maxx)
		{
			if (cul[minn]==-1)
			{
				cul[minn]=c[i];
				++num;
			}
			unesc(minn,minn+1);
			minn=find(minn);
		}
	}
}
inline void afis()
{
	int i;
	for (i=1; i<N; ++i)
		printf("%d\n",(cul[i]==-1)?0:cul[i]);
}
int main()
{
	freopen("curcubeu.in","r",stdin);
	freopen("curcubeu.out","w",stdout);
	scanf("%d%lld%lld%lld",&N,&a[1],&b[1],&c[1]);
	cul[1]=-1;
	gr[1]=1;
	for (int i=2; i<N; ++i)
	{
		gr[i]=i;
		cul[i]=-1;
		a[i]=i*a[i-1];
		b[i]=i*b[i-1];		
		c[i]=i*c[i-1];
		mod(a[i]);
		mod(b[i]);
		mod(c[i]);
	}
	gr[N]=N;
	color();
	afis();
	return 0;
}