Cod sursa(job #1456907)

Utilizator greenadexIulia Harasim greenadex Data 2 iulie 2015 13:21:40
Problema Curcubeu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("curcubeu.in");

const int MAX = 1000005;
int f[MAX], n, qa[MAX], qb[MAX], qc[MAX], col[MAX];

int find_root(int x) {
    int a = x;

    while (x != f[x])
        x = f[x];

    while (a != f[a]) {
        int temp = f[a];
        f[a] = x;
        a = temp;
    }

    return x;
}

void unite (int x, int y) {
    int a = find_root(x), b = find_root(y);
    f[min(a, b)] = max(a, b);
}


int main() {
    freopen("curcubeu.out", "w", stdout);
    fin >> n >> qa[1] >> qb[1] >> qc[1];
    col[0] = -1;
    col[1] = -1;
    col[n] = -1;
    f[1] = 1;
    for (int i = 2; i < n; i++) {
        col[i] = -1;
        f[i] = i;
        qa[i] = (1LL * qa[i - 1] * i) % n;
        qb[i] = (1LL * qb[i - 1] * i) % n;
        qc[i] = (1LL * qc[i - 1] * i) % n;


    }

    for (int i = n - 1; i >= 1; i--) {
        int x, y;
        for (x = max(1, min(qa[i], qb[i])), y = max(qb[i], qa[i]); x < y; ) {
            if(col[x] == -1)
                col[x] = qc[i];
            if (col[x - 1] != -1)
                unite(find_root(x - 1), find_root(x));
            x = find_root(x) + 1;
        }
        if(col[x] == -1)
            col[x] = qc[i];
        if (col[x - 1] != -1)
            unite(find_root(x - 1), find_root(x));
        if (col[x + 1] != -1)
            unite(find_root(x), find_root(x + 1));
        x = find_root(x) + 1;
    }

    for (int i = 1; i < n; i++) {
        if (col[i] == -1)
            col[i] = 0;
        printf("%d\n", col[i]);
    }

    return 0;
}