Cod sursa(job #3246552)

Utilizator teodora_lauraTeodora teodora_laura Data 3 octombrie 2024 17:03:55
Problema Curcubeu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.47 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cassert>
using namespace std;
typedef long long ll;

vector<int>parent, sol;
int n, m, mx = 0;
vector<pair<int, int>>v, q;

int get_root(int nod) {
	if (parent[nod] == nod)
		return nod;
	return parent[nod] = get_root(parent[nod]);
}
void merge(int x, int y) {
	x = get_root(x);
	y = get_root(y);
	if (x != y)
	{
		if (x > y)
			parent[y] = x;
		else
			parent[x] = y;
	}
}
void make_root(int nod) {
	parent[nod] = nod;
}


struct interval {
	int a, b, c;
};
signed main()
{
#ifdef INFOARENA
	freopen("curcubeu.in", "r", stdin);
	freopen("curcubeu.out", "w", stdout);
#endif

	int n, a, b, c;
	cin >> n >> a >> b >> c;
	sol.resize(n + 1, -1);
	parent.resize(n + 1, 0);

	vector<interval>pas;
	for (int i = 1; i <= n - 1; i++) {
		a = (1LL * a * i) % n;
		b = (1LL * b * i) % n;
		c = (1LL * c * i) % n;
		interval it;
		it.a = a;
		it.b = b;
		it.c = c;
		pas.push_back(it);
	}

	/*for (int i = 0; i < pas.size(); i++) {
		cout << pas[i].a << " " << pas[i].b << " " << pas[i].c << "\n";
	}*/
	for (int i = pas.size() - 1; i >= 0; i--) {
		//cout <<"pas " << pas[i].a << " " << pas[i].b << " " << pas[i].c << "\n";
		int start = min(pas[i].a, pas[i].b);
		int end = max(pas[i].a, pas[i].b);
		while (start <= end) {
			//cout << "sunt pe pozitia " << start << " care are sol[] " << sol[start] << "\n";
			if (sol[start] == -1)
			{
				sol[start] = pas[i].c;
				make_root(start);
				if (start + 1 <= n - 1 && parent[start + 1] != 0)
				{
					merge(start, start + 1);
					//cout << "ok cu +1\n";
				}
				if (start - 1 >= 1 && parent[start - 1] != 0)
				{
					merge(start, start - 1);
					//cout << "ok cu -1\n";
				}
				start++;
				//cout << "111111start sare la " << start << "\n";
			}
			else {
				start = get_root(start) + 1;
				//cout << "intru si aici bro\n";
			//cout << "222222start sare la " << start << "\n";
			}
			//cout << "\n";
		//cout <<"rad lui 8: " << get_root(8) << "rad lui 9: " << get_root(9) << " " << "rad lui 10: " << get_root(10) << "\n";
		}
		//cout << "GATA------------------------------------\n";

	}
	for (int i = 1; i <= n - 1; i++) {
		if (sol[i] != -1)
			cout << sol[i] << "\n";
		else
			cout << "0\n";
	}
}

/*

11  1 2 3
1 2 3
2 4 6
6 1 7
2 4 6
10 9 8
5 10 4
2 4 6
5 10 4
1 2 3
10 9 8
GATA
GATA

*/