Cod sursa(job #1490752)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 24 septembrie 2015 08:25:36
Problema Curcubeu Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <vector>
#include <fstream>
#include <numeric>
#include <utility>
using namespace std;

int main(){
	ifstream f("curcubeu.in");
	ofstream g("curcubeu.out");
	int n, a, b, c;
	f >> n >> a >> b >> c;
	vector<int> a_uri(n), b_uri(n), c_uri(n);
	a_uri[1] = a, b_uri[1] = b, c_uri[1] = c;
	for(int i = 2; i < n; ++i){
		a_uri[i] = ((long long)a_uri[i-1] * i) % n;
		b_uri[i] = ((long long)b_uri[i-1] * i) % n;
		c_uri[i] = ((long long)c_uri[i-1] * i) % n; }
	vector<int> rez(n, 0), next(n, 0);
	iota(begin(next), end(next), 1);
	for(int i = n-1; i >= 1; --i){
		int st = a_uri[i], dr = b_uri[i];
		if(st > dr){
			swap(st, dr); }
		for(int j = st, nxt; j <= dr; j = nxt){
			nxt = next[j];
			next[j] = max(next[j], dr+1);
			if(rez[j] == 0){
				rez[j] = c_uri[i]; } } }

	for(int i = 1; i < n; ++i){
		g << rez[i] << '\n'; }
	return 0; }