Cod sursa(job #565499)

Utilizator cosmyoPaunel Cosmin cosmyo Data 27 martie 2011 20:32:13
Problema Curcubeu Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>
using namespace std;
const int N = 1 << 20;
int  t[N], n, a, b, c;

struct tip{int st, dr, c, cl;} v[N];

inline int root(int x) {
    int r, y;
    for(r = x; r != t[r]; r = t[r]);

    for(;x != r; ) {
        y = t[x];
        t[x] = r;
        x = y;
    }

    return r;
}

inline void unite(int x, int y) {
    if(x < y) 
		t[x] = y;
	else
		t[y] = x;
}

int main() {
    ifstream fin("curcubeu.in");
    ofstream fout("curcubeu.out");
    int i;

    fin >> n >> a >> b >> c;
    for(i = 1; i < n; ++i) {
        if(a > b) {
			v[i].st = b;
			v[i].dr = a;
		}
		else {
			v[i].st = a;
			v[i].dr = b;
		}
        v[i].c = c;
        a = ((long long)a * (i + 1)) % n;
        b = ((long long)b * (i + 1)) % n;
        c = ((long long)c * (i + 1)) % n;
    }

    int  rd, j;

    for(i = 1; i <= n; ++i)
        t[i] = i;

    for(i = n - 1; i >= 1 ; --i) {


        rd = root(v[i].dr);
//		printf("%d\n", rd);
	
        for(j = v[i].st; j <= v[i].dr; ++j){
            if(v[j].cl == 0) {
                v[j].cl = v[i].c;
				t[j] = rd;
            }
			else 
				j = root(j);
	//		t[j] = rd;
        }

	}

    for(i = 1; i <= n - 1; ++i)
        fout << v[i].cl << '\n';

    return 0;
}