Cod sursa(job #1076477)

Utilizator SmarandaMaria Pandele Smaranda Data 10 ianuarie 2014 12:05:51
Problema Curcubeu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <cstdio>
#include <algorithm>

using namespace std;

const long N = 1000100;
long n, A [N], B [N], C [N], t [N], h [N], dr [N], c [N];

void read () {
	scanf ("%ld%ld%ld%ld", &n, &A [1], &B [1], &C [1]);
}

void generare () {
	long i;
	for (i = 2; i <= n; i ++) {
		A [i] = ((long long)A [i - 1] * i) % n;
		B [i] = ((long long)B [i - 1] * i) % n;
		C [i] = ((long long)C [i - 1] * i) % n;
	}
}

void init () {
	long i;
	for (i = 1; i < n; i ++) {
		t [i] = i;
		h [i] = 1;
		dr [i] = i;
	}
}

long getFather (long x) {
	long T, father;
	for (T = x; T != t [T]; T = t [T]);
	father = T;
	T = x;
	while (T != t [T]) {
		x = t [T];
		t [T] = father;
		T = x;
	}
	return father;
}

void union2 (long x, long y) {
	if (h [x] >= h [y])  {
		t [y] = x;
		dr [x] = max (dr [x], dr [y]);
	}
	else  {
		t [x] = y;
		dr [y] = max (dr [x], dr [y]);
	}
	if (h [x] == h [y])
		h [x] ++;
}

void solve () {
	long i, j, g, jj, lim, g1;
	generare ();
	init ();
	for (i = n - 1; i >= 1; i --) {
		j = min (A [i], B [i]);
		lim = max (A [i], B [i]);
		jj = j;
		g = getFather (j);
		g1 = getFather (j - 1);
		if (c [g] == 0 && c [j - 1] != 0)
			jj = g1;
		while (j <= lim) {
			g = getFather (j);
			if (c [g] == 0) {
				c [g] = C [i];
				union2 (getFather (jj), g);
			}
			j = dr [g] + 1;
		}
	}
	for (i = 1; i < n; i ++)
		printf ("%ld\n", c [i]);

}

int main () {

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

	read ();
	solve ();
	return 0;
}