Cod sursa(job #97682)

Utilizator wefgefAndrei Grigorean wefgef Data 7 noiembrie 2007 22:48:34
Problema Curcubeu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <cstdio>

const int Nmax = 1000005;

int n, m;
int a[Nmax], b[Nmax], c[Nmax];
int Next[Nmax];
int v[Nmax];
int st[Nmax], nr;

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

void ReadData() {
	freopen("curcubeu.in", "r", stdin);
	freopen("curcubeu.out", "w", stdout);

	scanf("%d %d %d %d", &n, &a[1], &b[1], &c[1]);
	for (int i = 2; i < n; ++i) {
		a[i] = (long long)a[i-1]*i%n;
		b[i] = (long long)b[i-1]*i%n;
		c[i] = (long long)c[i-1]*i%n;
	}
	for (int i = 1; i < n; ++i)
		if (a[i] > b[i]) swap(a[i], b[i]);
}

int FindNext(int p) {
	st[nr = 1] = p;
	while (Next[st[nr]] != st[nr]) {
		st[nr+1] = Next[st[nr]];
		++nr;
	}
	for (int i = 1; i <= nr; ++i)
		Next[st[i]] = st[nr];
	return Next[p];
}

void Solve() {
	for (int i = 1; i <= n+1; ++i)
		Next[i] = i;

	for (int i = n-1; i; --i)
		for (int j = FindNext(a[i]); j <= b[i]; j = Next[j]) {
			v[j] = c[i];
			Next[j] = FindNext(j+1);
		}
}

void WriteData() {
	for (int i = 1; i < n; ++i)
		printf("%d\n", v[i]);
}

int main() {
	ReadData();
	Solve();
	WriteData();
}