Cod sursa(job #940607)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 16 aprilie 2013 18:55:58
Problema Curcubeu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <stdlib.h>
#include <fstream>
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <string.h>
#include <iomanip>
#include <time.h>
#include <list>
#include <algorithm>
#include <math.h>
#include <assert.h>
using namespace std;


const string file = "curcubeu";

const string infile = file + ".in";
const string outfile = file + ".out";

#define MAXN 1000005
typedef unsigned long long ULL;

int Cul[MAXN];
int Next[MAXN];

int A[MAXN], B[MAXN], C[MAXN];
int N;


void citire()
{
	ifstream fin(infile.c_str());

	fin >> N >> A[1] >> B[1] >> C[1];

	fin.close();
}


inline void color(int a, int b, int c)
{

	int i = a;
	int aux;

	while( i <= b)
	{
		aux = Next[i];

		if(!Cul[i]) Cul[i] = c;

		if( b + 1 > Next[i]) Next[i] = b + 1;

		i = aux;
	}
}

void solve()
{
	if(A[1] > B[1]) A[1]^=B[1], B[1]^=A[1], A[1]^=B[1];

	Next[1] = 2;
	for(int i = 2; i < N; i++)
	{
		A[i] = ((ULL)A[i-1] * i) % N;
		B[i] = ((ULL)B[i-1] * i) % N;
		C[i] = ((ULL)C[i-1] * i) % N;

		if(A[i] > B[i])  A[i]^=B[i], B[i]^=A[i], A[i]^=B[i];
		Next[i] = i + 1;
	}

	for(int i = N-1; i >= 1; i--)
	{
		color(A[i], B[i], C[i]);
	}
}

void afisare()
{
	ofstream fout(outfile.c_str());

	for(int i = 1; i < N; i++)
	{
		fout << Cul[i] << "\n";
	}

	fout.close();
}

int main()
{
	citire();
	solve();
	afisare();
}