Cod sursa(job #87317)

Utilizator stef2nStefan Istrate stef2n Data 26 septembrie 2007 22:46:53
Problema Curcubeu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
//#define DEBUG

#include <cstdio>
#ifdef DEBUG
#include <iostream>
using namespace std;
#endif

#define NMAX 1000005
struct interval{int left,right,color;};

int N,A,B,C;
interval I[NMAX];
int color[NMAX],father[NMAX],next[NMAX];

inline int min(int x, int y)
{
	return (x<y)?x:y;
}

inline int max(int x, int y)
{
	return (x>y)?x:y;
}

void init()
{
	I[1].left=min(A,B);
	I[1].right=max(A,B);
	I[1].color=C;
	for(int i=2; i<N; i++)
	{
		A = ((long long) A * i) % (long long) N;
		B = ((long long) B * i) % (long long) N;
		C = ((long long) C * i) % (long long) N;
		I[i].left = min(A,B);
		I[i].right = max(A,B);
		I[i].color = C;
	}
#ifdef DEBUG
	cerr<<"Intervalele sunt:"<<endl;
	for(int i=1; i<N; i++)
		cerr<<I[i].left<<"->"<<I[i].right<<"	Cul="<<I[i].color<<endl;
	cerr<<endl;
#endif
	for(int i=1; i<N; i++)
		color[i]=0;
	for(int i=1; i<=N;i++)
	{
		father[i]=-1;
		next[i]=i;
	}
}

inline int root(int u)
{
	if(father[u]<0)
		return u;
	else
	{
		father[u]=root(father[u]);
		return father[u];
	}
}

inline void join(int u, int v) // u si v sunt 2 radacini
{
	if(father[u]<father[v]) // u mai adanc ca v
		father[v]=u;
	else
		if(father[u]>father[v]) // v mai adanc ca u
			father[u]=v;
		else // aceeasi adancime
		{
			father[u]=v;
			father[v]--;
		}
}

void solve()
{
	for(int k=N-1; k>=1; --k)
	{
		int r,aux;
		for(int i=I[k].left; i<=I[k].right ;)
		{
			r=root(I[k].right+1);
			aux=root(i);
			if(next[aux]==i) // necolorat
			{
				color[i]=I[k].color;
				join(aux,r);
				next[aux]=next[r];
				++i;
			}
			else
			{
				i=next[aux];
				if(aux!=r)
				{
					join(aux,r);
					next[aux]=next[r];
				}
			}
		}
	}
}


int main()
{
	freopen("curcubeu.in","r",stdin);
	freopen("curcubeu.out","w",stdout);
	scanf("%d %d %d %d",&N,&A,&B,&C);
	init();
	solve();
	for(int i=1; i<N; i++)
		printf("%d\n",color[i]);
	return 0;
}