Cod sursa(job #230375)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 13 decembrie 2008 19:39:34
Problema Curcubeu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include<stdio.h>

int n, nr, x[1000002], t[1000005], f[1000005];

typedef struct
{
	int a, b, c;
} culoare;
culoare v[1000002];

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

int get_root(int x)
{
	while (x != t[x]) x = t[x];
	return x;
}

void doit()
{
	int i;
	long long x;
	nr = n - 1; t[1] = f[1] = 1;
	for (i = 2; i < n; i++)
	{
		x = (long long)v[i - 1].a * i;
		v[i].a = x % n;
		x = (long long)v[i - 1].b * i;
		v[i].b = x % n;
		x = (long long)v[i - 1].c * i;
		v[i].c = x % n;
		t[i] = f[i] = i;
	}
}

int main()
{
	freopen("curcubeu.in","r",stdin);
	freopen("curcubeu.out","w",stdout);
	scanf("%d",&n);
	scanf("%d %d %d",&v[1].a, &v[1].b, &v[1].c);

	int i, j, xx, yy, tt;

	doit();	

	for (i = n - 1; i >= 1; i--)
	{
		xx = min(v[i].a, v[i].b);
		yy = max(v[i].a, v[i].b);
	
		int root = get_root(xx);
		j = f[root];			
		while (j <= yy)
		{			
			if (!x[j])
			{
				x[j] = v[i].c;
				nr--;								
			}
			if (x[j]) t[j] = root;
						
			tt = j;
			j = f[j] + 1;
			f[tt] = f[yy];
			
			if (!nr) break;
		}			
		if (!nr) break;
	}
	for (i = 1; i < n; i++) printf("%d\n",x[i]);
	return 0;
}