Cod sursa(job #1018815)

Utilizator harababurelPuscas Sergiu harababurel Data 29 octombrie 2013 23:23:43
Problema Curcubeu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 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++;
			s.erase(lo);
		}
		else t = s.find(lo);

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

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

	return 0;
}