Cod sursa(job #86013)

Utilizator gcosminGheorghe Cosmin gcosmin Data 23 septembrie 2007 13:35:30
Problema Curcubeu Scor 100
Compilator cpp Status done
Runda Autumn Warmup 2007, Runda 2 Marime 2.42 kb
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <list>
using namespace std;

#define NMAX 1000010

#define LL long long
int N, A, B, C, T;

int aa[NMAX];
int bb[NMAX];
int cc[NMAX];

int tata[NMAX];
int pr[NMAX];
int nr[NMAX];
int culf[NMAX];

char is_col[NMAX];

inline int MIN(int a, int b) { return (a < b) ? a : b; }
inline int MAX(int a, int b) { return (a > b) ? a : b; }

/*
int cul[NMAX * 4];
int tmp[NMAX * 4];

void update(int x, int y, int q)
{
	if (A <= x && y <= B) {
		cul[q] = C;
		tmp[q] = T;
		return;
	}

	int mij = (x + y) >> 1;

	if (A <= mij) update(x, mij, q << 1);
	if (B > mij) update(mij + 1, y, (q << 1) + 1);
}

void print_f(int x, int y, int q, int c, int t)
{
	if (tmp[q] > t) t = tmp[q], c = cul[q];

	if (x == y) {
		printf("%d\n", c);
		return;
	}

	int mij = (x + y) >> 1;

	print_f(x, mij, q << 1, c, t);
	print_f(mij + 1, y, (q << 1) + 1, c, t);
}

void sol1()
{
	int a, b;

	T = 1;

	a = A; b = B;

	A = MIN(a, b);
	B = MAX(a, b);

	update(1, N - 1, 1);

	A = a; B = b;

	for (T = 2; T < N; T++) {
		A = ((LL)A * T) % N;
		B = ((LL)B * T) % N;
		C = ((LL)C * T) % N;

		a = A; b = B;

		A = MIN(a, b);
		B = MAX(a, b);

		update(1, N - 1, 1);

		A = a; B = b;
	}

	print_f(1, N - 1, 1, -1, -1);
}
*/

inline int father(int x)
{
	if (tata[x] == x) return x;
	return tata[x] = father( tata[x] );
}

inline void unite(int x, int y)
{
	if (rand() & 1) tata[x] = y, nr[y] += nr[x], pr[y] = MIN(pr[x], pr[y]);
	else tata[y] = x, nr[x] += nr[y], pr[x] = MIN(pr[x], pr[y]);
}

int tt;
inline int get_next(int x)
{
	tt = father(x);

	return pr[tt] + nr[tt];
}

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

	scanf("%d %d %d %d", &N, &A, &B, &C);

/*	int a1 = A, b1 = B, c1 = C;
	sol1();
	A = a1; B = b1; C = c1;
*/
	aa[1] = MIN(A, B);
	bb[1] = MAX(A, B);
	cc[1] = C;

	for (T = 2; T < N; T++) {
		A = ((LL)A * T) % N;
		B = ((LL)B * T) % N;
		C = ((LL)C * T) % N;

		aa[T] = MIN(A, B);
		bb[T] = MAX(A, B);
		cc[T] = C;
	}

	int i, x;
	for (i = 1; i < N; i++) tata[i] = i, pr[i] = i, nr[i] = 1;

	for (i = N - 1; i >= 1; i--) {
		A = aa[i]; B = bb[i]; C = cc[i];

		x = A;

		if (is_col[x]) x = get_next(x);

		while (x <= B) {
			is_col[x] = 1;
			culf[x] = C;
			if (x > 1 && is_col[x - 1]) unite(father(x - 1), father(x));
			if (x < N - 1 && is_col[x + 1]) unite(father(x), father(x + 1));

			x = get_next(x);
		}
	}

	for (i = 1; i < N; i++) printf("%d\n", culf[i]);

return 0;
}