Cod sursa(job #86315)

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

using namespace std;
int tree[6*2000000];
int col[1000001];
int N;
struct nod {
	int A, B, C;
	nod(){};
	nod(int a, int b, int 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;
	baga(2*nod, a, (a+b)/2, pa, pb);
	baga(2*nod+1, (a+b)/2+1, b, pa, pb);
	tree[nod] = tree[2*nod] + tree[2*nod+1];
};
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("%d %d %d", &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 >= 0; --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) printf("%d\n", col[i]-1);
	//scanf("%d", &col[0]);
	return 0;
};