Cod sursa(job #3257652)

Utilizator luc3lexa_Alexandrescu Luca luc3lexa_ Data 18 noiembrie 2024 19:17:33
Problema Curcubeu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("curcubeu.in");
ofstream fout("curcubeu.out");

const int nmax = 1e6+10;

vector<int> a(nmax,0),b(nmax,0),c(nmax,0),ans(nmax,0),parent(nmax,0);
int n,value_a,value_b,value_c;

void read_input(){
	fin >> n >> value_a >> value_b >> value_c;
}

void precalculare(){
	a[1] = min(value_a,value_b);
	b[1] = max(value_a,value_b);
	c[1] = value_c;
	
	for(int i = 2; i <=n-1; i++){
		a[i] = (1LL*a[i-1] * i)%n;
		b[i] = (1LL*b[i-1] * i)%n;
		c[i] = (1LL*c[i-1] * i)%n;
		
		if(b[i] < a[i]){
			swap(a[i],b[i]);
		}
	}
	
	for(int i = 0; i <=n; i++){
		parent[i] = i;
	}
}

int find_parent(int nod){
	if(parent[nod] == nod){
		return nod;
	}else{
		return parent[nod] = find_parent(parent[nod]);
	}
}

void solve(){
	for(int i = n-1; i >=1;i--){
		int curr_pos = find_parent(a[i]);
		while(curr_pos <= b[i]){
			ans[curr_pos] = c[i];
			parent[curr_pos] = b[i]+1;
			curr_pos = find_parent(curr_pos+1);
		}
	};
	
	for(int i = 1; i <=n-1;i++){
		fout << ans[i] << '\n';
	}
}

int main(){
	read_input();
	precalculare();
	solve();
	return 0;
}