Cod sursa(job #257493)

Utilizator scvalexAlexandru Scvortov scvalex Data 13 februarie 2009 14:08:00
Problema Curcubeu Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <stdio.h>

int N;
int C[1000001], next[1000001], a[1000001], b[1000001], c[1000001];

inline int find_progenitor(int x) {
	int y = x, aux;
	for (; next[x] != x; x = next[x])
		;
	for (; next[y] != y; y= aux) {
		aux = next[y];
		next[y] = x;
	}
	return x;
}

int main(int argc, char *argv[]) {
	int i, ac, bc, j;

	FILE *fi = fopen("curcubeu.in", "r");
	fscanf(fi, "%d %d %d %d", &N, a+1, b+1, c+1);
	fclose(fi);

	for (i = 2; i < N; ++i) {
		a[i] = ((long long)a[i-1] * (long long)i) % (long long)N;
		b[i] = ((long long)b[i-1] * (long long)i) % (long long)N;
		c[i] = ((long long)c[i-1] * (long long)i) % (long long)N;
	}

	for (i = 1; i <= N; ++i) 
		next[i] = i;

	for (i = N-1; i >= 1; --i) {
		if (a[i] > b[i]) {
			ac = b[i];
			bc = a[i];
		} else {
			ac = a[i];
			bc = b[i];
		}
		
		for (j = find_progenitor(ac); j <= bc; j = next[j]) {
			C[j] = c[i];
			next[j] = find_progenitor(j+1);
		}
	}

	FILE *fo = fopen("curcubeu.out", "w");
	for (i = 1; i < N; ++i)
		fprintf(fo, "%d\n", C[i]);
	fclose(fo);

	return 0;
}