Cod sursa(job #1618591)

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

using namespace std;

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

const int N = 1000010;

class disjointSet {
private:
    int n;
    int f[N];
    int r[N];
public:
    int _right[N];
    void _clear(int _n) {
        n = _n;
        for(int i = 1; i <= n; i++) {
            f[i] = i;
            r[i] = 1;
            _right[i] = i;
        }
    }
    disjointSet(int _n = 0) {
        _clear(n);
    }
    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 _final[N];
stack < int > st_a, st_b, st_c;
disjointSet _set;

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

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

    _set._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;
            _set._merge(j, j + 1);
            j = _set._right[_set.get_father(j)];
        }
    }

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

    return 0;
}