Cod sursa(job #2924026)

Utilizator lolismekAlex Jerpelea lolismek Data 23 septembrie 2022 11:38:41
Problema Curcubeu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int N = 1e6;
int v[N + 1], root[N + 1];
bool f[N + 1];

int Find(int i){
	if(root[i] == i)
		return i;
	return (root[i] = Find(i));
}

struct Query{
	int l, r, val;
	
	void clean(){
		if(l > r)
			swap(l, r);
	}
};

Query q[N + 1];

int main(){

	int n;
	fin >> n >> q[1].l >> q[1].r >> q[1].val;

	q[1].clean();

	for(int i = 2; i <= n - 1; i++)
		q[i].l = (q[i - 1].l * i) % n,
		q[i].r = (q[i - 1].r * i) % n,
		q[i].val = (q[i - 1].val * i) % n, 
		q[i].clean();

	n--;

	for(int i = 1; i <= n; i++)
		root[i] = i;

	for(int i = n; i >= 1; i--){
		int j = q[i].l;
		while(j <= q[i].r){
			int newJ = Find(j) + 1;
			if(!f[j])
				f[j] = true, v[j] = q[i].val, root[j] = j + 1;
			j = newJ;
		}
	}	

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

	return 0;
}