Cod sursa(job #972636)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 12 iulie 2013 12:14:49
Problema Curcubeu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <fstream>
using namespace std;

const int MAX_N = 1000002;

int N;
int a[MAX_N], v[MAX_N][3], F[MAX_N];
long long int A, B, C;

inline int find(int x) {
    int R = x;
    while(R != F[R])
        R = F[R];
    while(x != F[x]) {
        int temp = F[x];
        F[x] = R;
        x = temp;
    }

    return R;
}

inline void unite(int x, int y) {
    F[y] = x;
}

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

    f >> N >> A >> B >> C;
    v[1] = {A, B, C};
    for(int i = 2; i < N; ++i) {
        A = ((long long) A * i) % N;
        B = ((long long) B * i) % N;
        C = ((long long) C * i) % N;
        int t1 = min(A, B), t2 = max(A, B);
        A = t1, B = t2;
        v[i] = {A, B, C};
    }

    for(int i = 1; i <= N; ++i)
        F[i] = i;
    for(int i = N - 1; i; --i) {
        for(int j = v[i][0]; j <= v[i][1]; ++j)
            if(F[j] != j) {
                if(find(j) < find(v[i][1]))
                    unite(find(v[i][1]), find(j));
                else if(find(v[i][1]) < find(j))
                    unite(find(j), find(v[i][1]));
                j = F[j];
            }
            else
                a[j] = v[i][2], F[j] = v[i][1];

    }

    for(int i = 1; i < N; ++i)
        g << a[i] << '\n';

    f.close();
    g.close();

    return 0;
}