Cod sursa(job #86674)

Utilizator victorsbVictor Rusu victorsb Data 25 septembrie 2007 10:59:10
Problema Curcubeu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define Nmax 1000005

int n, ct;
int a[Nmax], b[Nmax], c[Nmax];
int sir[Nmax];
int t[Nmax];
int h[Nmax];
int d[Nmax];

int mul(int a, int b)
{
	long long tmp;

	tmp = a;
	tmp *= b;
	tmp %= n;

	return tmp;
}

void citire()
{
	int i;

	scanf("%d %d %d %d", &n, &a[1], &b[1], &c[1]);
	for (i = 2; i < n; ++i)
	{
		a[i] = mul(a[i - 1], i);
		b[i] = mul(b[i - 1], i);
		c[i] = mul(c[i - 1], i);
	}
}

int find(int nod)
{
	if (t[nod] != nod)
		t[nod] = find(t[nod]);

	return t[nod];
}

void uneste(int a, int b)
{
	if (h[a] > h[b])
	{
		t[b] = a;
		d[a] = max(d[a], d[b]);
	}
	else
	{
		t[a] = b;
		d[b] = max(d[a], d[b]);
		if (h[a] == h[b]) ++h[b];
	}
}

void solve()
{
	int i, pos, st, dr;

	--n;
	for (i = n; i >= 1; --i)
	{
		st = min(a[i], b[i]);
		dr = max(a[i], b[i]);

		pos = st - 1;
		while (pos < dr)
		{
			++pos;
			if (find(pos))
				pos = d[find(pos)];
			else
			{
				sir[pos] = c[i];
				t[pos] = pos;
                d[pos] = pos;
				if (pos - 1 >= 1 && find(pos - 1)) uneste(find(pos - 1), find(pos));
				if (pos + 1 <= n && find(pos + 1)) uneste(find(pos), find(pos + 1));
			}
		}
	}

	for (i = 1; i <= n; ++i)
		printf("%d\n", sir[i]);
}

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

	citire();
	solve();

	return 0;
}