Cod sursa(job #86015)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 23 septembrie 2007 13:36:17
Problema Curcubeu Scor 100
Compilator cpp Status done
Runda Autumn Warmup 2007, Runda 2 Marime 1.48 kb
#include <cstdio>
#include <cstdlib>
#include <vector>

using namespace std;

#define MAXN 1000005

int N, A, B, C;
vector<int> a, b, c;

int p[MAXN], biggest[MAXN], col[MAXN];

inline int getSet( int x )
{
	if (p[x] == x) return x;
	return p[x] = getSet( p[x] );
}

inline void unite( int a, int b )
{
	a = getSet(a);
	b = getSet(b);

	if (a == b) return;
	if (rand() % 2)
	{
		p[b] = a;
		if (biggest[b] > biggest[a])
			biggest[a] = biggest[b];
	}
	else
	{
		p[a] = b;
		if (biggest[a] > biggest[b])
			biggest[b] = biggest[a];
	}
}

int main()
{
	freopen("curcubeu.in", "rt", stdin);
	freopen("curcubeu.out", "wt", stdout);

	scanf("%d %d %d %d", &N, &A, &B, &C);

	a.reserve(N); b.reserve(N); c.reserve(N);

	a.push_back(A);	b.push_back(B);	c.push_back(C);

	for (int i = 2; i <= N - 1; i++)
	{
		A = (int)(((long long)A * i) % N);
		B = (int)(((long long)B * i) % N);
		C = (int)(((long long)C * i) % N);

		a.push_back(A);
		b.push_back(B);
		c.push_back(C);
	}

	for (int k = 1; k < N; k++)
		p[k] = k, biggest[k] = k, col[k] = -1;

	for (int k = (int)a.size() - 1; k >= 0; k--)
	{
		int l = min(a[k], b[k]), r = max(a[k], b[k]);

		int mother = getSet(l), p = biggest[mother] + 1;
		if (col[l] == -1)		//mother == l
			col[l] = c[k];

		for (; p <= r; )
		{
			if (col[p] == -1)
				col[p] = c[k];
			unite( mother, p );
			mother = getSet(mother);

			p = biggest[ mother ] + 1;
		}
	}

	for (int k = 1; k < N; k++)
		if (col[k] == -1)
			printf("0\n");
		else
			printf("%d\n", col[k]);

	return 0;
}