Cod sursa(job #85316)

Utilizator wefgefAndrei Grigorean wefgef Data 20 septembrie 2007 21:29:15
Problema Curcubeu Scor Ascuns
Compilator cpp Status done
Runda Marime 1.37 kb
#include <cstdio>

const int Nmax = 1000005; 

int a, b, c;
int seg[4*Nmax];
char bun[4*Nmax];
int v[Nmax];

void update(int poz, int st, int dr) {
	if (a <= st && dr <= b) {
		seg[poz] = c;
		bun[poz] = 1;
		return;
	}
	int m = (st+dr)/2, p1 = poz*2, p2 = poz*2+1;
	if (bun[poz]) {
		seg[p1] = seg[p2] = seg[poz];
		bun[p1] = bun[p2] = 1;
		bun[poz] = 0;
	}
	if (a <= m) update(p1, st, m);
	if (b > m) update(p2, m+1, dr);
}

void reconst(int poz, int st, int dr) {
	if (bun[poz]) {
		for (int i = st; i <= dr; ++i)
			v[i] = seg[poz];
		return;
	}
	int m = (st+dr)/2, p1 = poz*2, p2 = poz*2+1;
	reconst(p1, st, m);
	reconst(p2, m+1, dr);
}

inline void swap(int &a, int &b) { a ^= b ^= a ^= b; }

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

	seg[1] = 0; bun[1] = 1;

	int n, A, B;
	scanf("%d %d %d %d", &n, &A, &B, &c);
	a = A, b = B;
	if (a > b) swap(a, b);
	update(1, 1, n-1);

	for (int i = 2; i < n; ++i) {
		long long aux;

		aux = A;
		aux *= static_cast<long long>(i);
		aux %= static_cast<long long>(n);
		A = aux;

		aux = B;
		aux *= static_cast<long long>(i);
		aux %= static_cast<long long>(n);
		B = aux;

		aux = c;
		aux *= static_cast<long long>(i);
		aux %= static_cast<long long>(n);
		c = aux;

		a = A, b = B;
		if (a > b) swap(a, b);
		update(1, 1, n-1);
	}
	reconst(1, 1, n-1);
	for (int i = 1; i < n; ++i)
		printf("%d\n", v[i]); 
}