Cod sursa(job #3367912)

Utilizator DobraVictorDobra Victor Ioan DobraVictor Data 12 octombrie 2026 09:27:57
Problema Curcubeu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <iostream>
#include <fstream>
#include <stdint.h>

const int32_t MAX_N = 1000000;

int32_t min(int32_t x, int32_t y) {
	return (x < y) ? x : y;
}
int32_t max(int32_t x, int32_t y) {
	return (x > y) ? x : y;
}

struct Update {
	int32_t left, right;
	int32_t color;
};
struct DSF {
	struct Node {
		int32_t parent;
		int32_t color;
		int32_t next;
	};

	int32_t n;
	Node nodes[MAX_N];

	void Init(int32_t n) {
		this->n = n;
		for(int32_t i = 0; i != n; ++i) {
			nodes[i].parent = -1;
			nodes[i].color = 0;
			nodes[i].next = i + 1;
		}
	}
	int32_t GetRoot(int32_t node) {
		if(nodes[node].parent == -1)
			return node;
		int32_t root = GetRoot(nodes[node].parent);
		nodes[node].parent = root;
		return root;
	}
	int32_t Merge(int32_t root1, int32_t root2) {
		nodes[root1].parent = root2;
		return root2;
	}
};

int32_t n;
Update updates[MAX_N];
DSF dsf;

void GenUpdates(std::istream& fin) {
	int32_t a, b, c;
	fin >> n >> a >> b >> c;

	for(int32_t i = 0; i != n; ++i) {
		updates[i].left = min(a, b);
		updates[i].right = max(a, b);
		updates[i].color = c;

		a = ((int64_t)a * (i + 2)) % n;
		b = ((int64_t)b * (i + 2)) % n;
		c = ((int64_t)c * (i + 2)) % n;
	}
}
void AssignColors() {
	for(int32_t i = n - 1; i != -1; --i) {
		int32_t ind = updates[i].left;
		int32_t root = dsf.GetRoot(ind);
		if(dsf.nodes[root].color == 0)
			dsf.nodes[root].color = updates[i].color;
		ind = dsf.nodes[root].next;

		for(; ind <= updates[i].right; ind = dsf.nodes[root].next) {
			int32_t newRoot = dsf.GetRoot(ind);
			if(dsf.nodes[newRoot].color == 0)
				dsf.nodes[newRoot].color = updates[i].color;
			root = dsf.Merge(root, newRoot);
		}
	}
}
void OutputRes(std::ostream& fout) {
	for(int32_t i = 1; i != n; ++i)
		fout << dsf.nodes[i].color << '\n';
}

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

	GenUpdates(fin);
	dsf.Init(n);
	AssignColors();
	OutputRes(fout);

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

	return 0;
}