Cod sursa(job #1618614)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 27 februarie 2016 21:51:31
Problema Curcubeu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <fstream>
#include <algorithm>
#include <stack>

using namespace std;

ifstream in("curcubeu.in");
ofstream out("curcubeu.out");

const int N = 1000010;

int n;
int f[N];
int r[N];
int _right[N];
int _final[N];
stack < int > st_a, st_b, st_c;

void _clear(int _n) {
    n = _n;
    for(int i = 1; i <= n; i++) {
        f[i] = i;
        r[i] = 1;
        _right[i] = i;
    }
}

int get_father(int x) {
        if(x != f[x]) {
        f[x] = get_father(f[x]);
    }
    return f[x];
}

void _merge(int x, int y) {
    int root_x, root_y;

    root_x = get_father(x);
    root_y = get_father(y);

    if(root_x != root_y) {
        if(r[root_x] < r[root_y]) {
            f[root_x] = root_y;
            _right[root_y] = max(_right[root_y], _right[root_x]);
        }
        else if(r[root_x] > r[root_y]) {
            f[root_y] = root_x;
            _right[root_x] = max(_right[root_x], _right[root_y]);
        }
        else {
            f[root_x] = root_y;
            _right[root_y] = max(_right[root_y], _right[root_x]);
            r[root_y]++;
        }
    }
}



int main() {
    int a, b, c, i, j, start, fin;

    in >> n >> a >> b >> c;

    _clear(n);

    st_a.push(a);
    st_b.push(b);
    st_c.push(c);

    for(i = 2; i < n; i++) {
        a = (i * a) % n;
        b = (i * b) % n;
        c = (i * c) % n;

        st_a.push(a);
        st_b.push(b);
        st_c.push(c);
    }

    for(i = 1; i < n; i++) {
        a = st_a.top();
        b = st_b.top();
        c = st_c.top();

        st_a.pop();
        st_b.pop();
        st_c.pop();

        start = min(a, b);
        fin = max(a, b);
        j = start;
        while(j < fin) {
            _final[j] = c;
            j = _right[get_father(j)];
            _merge(j, j + 1);
        }
        if(j == fin) {
            _final[fin] = c;
        }
    }

    for(i = 1; i < n; i++) {
        out << _final[i] << '\n';
    }

    return 0;
}