Cod sursa(job #277635)

Utilizator tvladTataranu Vlad tvlad Data 11 martie 2009 20:18:18
Problema Curcubeu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <cstdio>

const int NMAX = 1000000;

int n;
int a[NMAX], b[NMAX], c[NMAX];
int v[NMAX], skip[NMAX];

int main() {
	freopen("curcubeu.in","rt",stdin);
	freopen("curcubeu.out","wt",stdout);
	scanf("%d %d %d %d",&n,&a[1],&b[1],&c[1]);
	for (int i = 2; i < n; ++i) {
		a[i] = (a[i-1] * i) % n; --a[i-1];
		b[i] = (b[i-1] * i) % n;
		c[i] = (c[i-1] * i) % n;
	}
	--n; --a[n];

	for (int i = 0; i < n; ++i) skip[i] = i;
	bool complete = false;
	for (int k = n; k > 0; --k) {
		if (b[k] < a[k])
			a[k] ^= b[k] ^= a[k] ^= b[k];
		int i = a[k];
		while (skip[i] != i) {
			int next, aux;
			for (next = i, aux = 0; skip[next] != next && aux < n; next = skip[next], ++aux);
			if (aux == n) {
				complete = true;
				break;
			}
			for (int p = i; skip[p] != p; aux = skip[p], skip[p] = next, p = aux);
			i = next;
		}
		while (i < b[k]) {
			if (complete) break;
			v[i] = c[k];
			skip[i] = skip[i+1];
			while (skip[i] != i) {
				int next, aux;
				for (next = i, aux = 0; skip[next] != next && aux < n; next = skip[next], ++aux);
				if (aux == n) {
					complete = true;
					break;
				}
				for (int p = i; skip[p] != p; aux = skip[p], skip[p] = next, p = aux);
				i = next;
			}
		}
		if (complete) break;
	}

	for (int i = 0; i < n; ++i)
		printf("%d\n",v[i]);
	return 0;
}