Cod sursa(job #490261)

Utilizator darrenRares Buhai darren Data 5 octombrie 2010 18:44:40
Problema Curcubeu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#include <algorithm>

using namespace std;

int N;
int A[1000002], B[1000002], C[1000002];
int Color[1000002];
int Till[1000002];

int main()
{
	ifstream fin("curcubeu.in");
	ofstream fout("curcubeu.out");

	fin >> N;
	fin >> 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 = N - 1; i >= 1; --i)
	{
		int beg = min(A[i], B[i]);
		int end = max(A[i], B[i]);

		for (int j = beg; j <= end; ++j)
		{
			int init = j;
			while (Color[j])
				j = Till[j] + 1;
			while (Color[init])
			{
				int aux = init;
				init = Till[init] + 1;
				Till[aux] = j - 1;
			}

			if (j <= end)
			{
				Color[j] = C[i];
				Till[j] = end;
			}
		}
	}

	for (int i = 1; i < N; ++i)
		fout << Color[i] << '\n';

	fin.close();
	fout.close();
}