Cod sursa(job #972752)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 12 iulie 2013 16:42:24
Problema Curcubeu Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <fstream>
using namespace std;

const int MAX_N = 1000002;

int N;
int a[MAX_N], v[MAX_N][3], F[MAX_N], H[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) {
    if(x > y)
        F[y] = x;
    else F[x] = y;
}

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

    f >> N >> A >> B >> C;
    v[1][0] = A, v[1][1] = B, v[1][2] = C, F[1] = 1, H[1] = 1;
    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 temp;
        if(A > B)
            temp = A, A = B, B = temp;
        v[i][0] = A, v[i][1] = B, v[i][2] = C;
        F[i] = i, H[i] = 1;
    }

    for(int i = N - 1; i; --i) {
        for(int j = v[i][0]; j <= v[i][1]; ++j)
            if(F[j] != j) {
                unite(find(v[i][1]), find(j));
                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;
}