Cod sursa(job #86320)

Utilizator vlad_DVlad Dumitriu vlad_D Data 24 septembrie 2007 00:45:48
Problema Curcubeu Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <cstdio>
#include <algorithm>

using namespace std;
int tree[6*2000000];
int col[1000001];
int N;
struct nod {
	long A, B, C;
	nod(){};
	nod(long a, long b, long c) {A = a; B = b; C = c;};
};
nod IZ[1000002];
int colorez;
void baga(int nod, int a, int b, int pa, int pb) {
	if(a > b) return;
	if(pa > b || pb < a) return;
	if(a == b) {if (!col[a]) {col[a] = colorez; tree[nod] = 1;} return;};
	if(tree[nod] == b - a + 1) return;
	int ret = 0;
	if (a <= (a+b)/2) {
		baga(2*nod, a, (a+b)/2, pa, pb);
		ret+=tree[2*nod];
	}
	if ((a+b)/2+1 <= b) {
		baga(2*nod+1, (a+b)/2+1, b, pa, pb);
		ret+=tree[2*nod+1];
	}
	tree[nod] = ret;
};
int main() {
	
	freopen("curcubeu.in", "r", stdin);
	freopen("curcubeu.out", "w", stdout);
	
	/*Ai = (Ai-1 * i) % N
	Bi = (Bi-1 * i) % N
	Ci = (Ci-1 * i) % N*/
	scanf("%d", &N);
	scanf("%ld %ld %ld", &IZ[0].A, &IZ[0].B, &IZ[0].C);
	int i;
	for (i = 1; i + 1 < N; ++i){
		IZ[i].A = long(long(IZ[i-1].A) * long(i+1)) % N;
		IZ[i].B = long(long(IZ[i-1].B) * long(i+1)) % N;
		IZ[i].C = long(long(IZ[i-1].C) * long(i+1)) % N;
	};
	for (i = N - 2; i > -1; --i) {
		colorez = IZ[i].C + 1;
		//printf("%d %d %d\n", IZ[i].A, IZ[i].B, IZ[i].C);
		baga(1, 0, N, min(IZ[i].A, IZ[i].B), max(IZ[i].A, IZ[i].B));
	};
	for (i = 1; i < N; ++i) {if (col[i] == 0) col[i] = 1; printf("%d\n", col[i]-1);}
	//scanf("%d", &col[0]);
	return 0;
};