Cod sursa(job #1456920)

Utilizator greenadexIulia Harasim greenadex Data 2 iulie 2015 13:44:18
Problema Curcubeu Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("curcubeu.in");

const int MAX = 1000005;
int f[MAX], n, qa[MAX], qb[MAX], qc[MAX], col[MAX];

int find_root(int x) {
	int a = x;

	while (x != f[x])
		x = f[x];

	while (a != f[a]) {
		int temp = f[a];
		f[a] = x;
		a = temp;
	}

	return x;
}

void unite (int x, int y) {
	int a = find_root(x), b = find_root(y);
	f[a] = b;
}

int main() {
	freopen("curcubeu.out", "w", stdout);
	fin >> n >> qa[1] >> qb[1] >> qc[1];
	col[0] = -1;
	col[1] = -1;
	col[n] = -1;
	f[1] = 1;
	for (int i = 2; i < n; i++) {
		col[i] = -1;
		f[i] = i;
		qa[i] = (1LL * qa[i - 1] * i) % n;
		qb[i] = (1LL * qb[i - 1] * i) % n;
		qc[i] = (1LL * qc[i - 1] * i) % n;
	}

	for (int i = n - 1; i >= 1; i--) {
		int x, y;
		for (x = max(1, min(qa[i], qb[i])), y = max(qb[i], qa[i]); x < y; ) {
			int stuff = find_root(x);
			if (col[x] == -1)
				col[x] = qc[i];
			if (col[x - 1] != -1)
				unite(find_root(x - 1), stuff);
			x = stuff + 1;
		}
		if (x == y) {
			int stuff = find_root(x);
			if (col[x] == -1)
				col[x] = qc[i];
			if (col[x - 1] != -1)
				unite(find_root(x - 1), stuff);
			if (col[x + 1] != -1)
				unite(stuff, find_root(x + 1));
		}
	}

	for (int i = 1; i < n; i++)
		printf("%d\n", (col[i] == -1) ? 0 : col[i]);

	return 0;
}