Cod sursa(job #1490744)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 24 septembrie 2015 08:12:11
Problema Curcubeu Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <vector>
#include <fstream>
#include <utility>
using namespace std;

class max_aint{
	int n;
	vector<int> v;
public:
	max_aint(const int N): n(N), v(2*n, 0){}
	void update(int st, int dr, const int val){
		for(st += n, dr += n+1; st < dr; st /= 2, dr /= 2){
			if(st%2 == 1){
				v[st] = max(v[st], val);
				++st; }
			if(dr%2 == 1){
				--dr;
				v[dr] = max(v[dr], val); } } }
	int query(int p){
		int rez = 0;
		for(p += n; p > 0; p /= 2){
			rez = max(rez, v[p]); }
		return rez; } };

int main(){
	ifstream f("curcubeu.in");
	ofstream g("curcubeu.out");
	int n, a, b, c;
	f >> n >> a >> b >> c;
	max_aint mai(n);
	vector<int> culori(n, 0);
	for(int i = 1; i < n; ++i, a = (a*i)%n, b = (b*i)%n, c = (c*i)%n){
		if(a > b){
			swap(a, b); }
		culori[i] = c;
		mai.update(a, b, i); }
	for(int i = 1; i < n; ++i){
		g << culori[mai.query(i)] << '\n'; }
	return 0; }