Cod sursa(job #1742645)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 16 august 2016 20:15:53
Problema Curcubeu Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <fstream>
#include <algorithm>
using namespace std;

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

const int MAXN = 1000005;

int a[1 + MAXN], b[1 + MAXN], c[1 + MAXN];
int limit[1 + MAXN], h[1 + MAXN], dad[1 + MAXN], color[1 + MAXN];

int FindDad(int node) {
    int current = node;
    while (node != dad[node])
        node = dad[node];
    while (current != node) {
        int temp = dad[current];
        dad[current] = node;
        current = temp;
    }
    return node;
}

void Join(int a, int b) {
    if (h[a] > h[b]) {
        dad[b] = a;
        limit[a] = max(limit[a], limit[b]);
    }
    else {
        dad[a] = b;
        limit[b] = max(limit[a], limit[b]);
    }
    if (h[a] == h[b])
        h[b]++;
}

int main() {
    int n;
    cin >> n >> a[1] >> b[1] >> c[1];
    for (int i = 2; i <= n - 1; i++) {
        a[i] = (1LL * i * a[i - 1]) % n;
        b[i] = (1LL * i * b[i - 1]) % n;
        c[i] = (1LL * i * c[i - 1]) % n;
    }
    for (int i = n - 1; i >= 1; i--) {
        int left = min(a[i], b[i]);
        int right = max(a[i], b[i]);
        for (int j = left; j <= right; j++)
            if (dad[j] == 0) {
                dad[j] = j;
                limit[j] = j;
                if (dad[j - 1] != 0)
                    Join(FindDad(j), FindDad(j - 1));
                color[j] = c[i];
            }
            else {
                if (dad[j - 1] != 0)
                    Join(FindDad(j), FindDad(j - 1));
                j = limit[FindDad(j)];
            }
    }
    for (int i = 1; i <= n - 1; i++)
        cout << color[i] << "\n";
    return 0;
}