Cod sursa(job #1019350)

Utilizator harababurelPuscas Sergiu harababurel Data 30 octombrie 2013 22:57:53
Problema Curcubeu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
//O(n log n)
#include <iostream>
#include <fstream>
#include <set>
#define nmax 1000005
using namespace std;

int n, lo, hi, color;
int a[nmax], b[nmax], c[nmax], v[nmax];
set <int> s;
set <int>::iterator t;

int main() {
	ifstream f("curcubeu.in");
	ofstream g("curcubeu.out");

	f>>n>>a[1]>>b[1]>>c[1];
	for(int i=2; i<n; i++) {
		a[i] = (a[i-1] * i) % n;
		b[i] = (b[i-1] * i) % n;
		c[i] = (c[i-1] * i) % n;
	}

	for(int i=1; i<n; i++) s.insert(i);

	for(int i=n-1; i>=1; i--) {
		lo = min(a[i], b[i]);
		hi = max(a[i], b[i]);
		color = c[i];

		if(s.find(lo) == s.end()) {
			s.insert(lo);
			t = s.find(lo);
			t++;
		}
		else t = s.find(lo);

		while(t != s.end() && *t <= hi) {
			v[*t] = color;
			t++;
		}
        if(s.find(hi) == s.end()) s.insert(hi);

		s.erase(s.find(lo), s.find(hi));
	}

	for(int i=1; i<n; i++) g<<v[i]<<" ";
	g<<"\n";

	return 0;
}