Cod sursa(job #3167070)

Utilizator leelcheeseCiovnicu Denis leelcheese Data 9 noiembrie 2023 22:26:43
Problema Curcubeu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
#define ll long long 
#define ull unsigned long long 
#define nmax 1001006
#define MOD 666013 
#define INF 2345678901
//#define fin cin 
//#define fout cout 

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

int n, A, B, C;
int col[nmax];
int t[nmax];

/**
Ai = (Ai-1 * i) % N
Bi = (Bi-1 * i) % N
Ci = (Ci-1 * i) % N


test: 3 2 2 1

i  1 2 3 4 5 6 7 8 9
A= 2 1
B= 2 1
C= 1 2


i    1 2
col  2 1

test: 5 3 2 1

i  1 2 3 4 5 6 7 8 9
A= 3 1 3 2
B= 2 4 2 3
C= 1 2 1 4


i    1 2 3 4
col  2 4 4 2

?schimb culoarea doar la radacina?
**/

int findRoot(int x)
{
	int y, rad;
	rad = x;
	while (t[rad] != 0)
		rad = t[rad];
	while (x != rad)
	{
		y = t[x];
		t[x] = rad;
		x = y;
	}
	return rad;
}

void Union(int x, int y)
{
	col[x] = C;
	if (x == y)
		return;
	t[y] = x;
}

//void af()
//{
//	int i;
//	for (i = 1; i < n; i++)
//		fout << col[i] << " ";
//	fout << "\n";
//}

int main()
{
	int i, j, x, y;
	fin >> n >> A >> B >> C;
	for (i = 1; i < n; i++)
	{
		A = (A * i) % n;
		B = (B * i) % n;
		C = (C * i) % n;
		x = min(A, B);
		y = max(A, B);
		col[x] = C;
		/*fout << "rad: " << x << " " << y << "   col: " << C << "\n";*/
		Union(x, y);
		/*af();*/
	}
	for (i = 1; i < n; i++)
	{
		x = findRoot(i);
		fout << col[x] << "\n";
	}
	fin.close();
	fout.close();
	return 0;
}