Cod sursa(job #2224840)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 25 iulie 2018 12:24:13
Problema Curcubeu Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1000000 + 5;
int N;

int A[NMAX], B[NMAX], C[NMAX];
int color[NMAX];

// Paduri
int father[NMAX], h[NMAX];
int rgt[NMAX];

inline void init() { for (int i = 1; i < N; ++ i) father[i] = rgt[i] = i; }

inline int find(int node) {
    if (father[node] != father[father[node]])
        father[node] = find(father[node]);
    return father[node];
}

inline void unite(int a, int b) {
    a = find(a), b = find(b);
    if (a == b)
        return ;
    if (h[b] > h[a])
        swap(a, b);
    father[b] = a;
    if (h[a] == h[b])
        ++ h[a];
    rgt[a] = max(rgt[a], rgt[b]);
}

void paint(int a, int b, int c) {
    if (color[a])
        a = rgt[find(a)] + 1;
    while (a <= b) {
        color[a] = c;
        if (color[a - 1])
            unite(a - 1, a);
        if (color[a + 1])
            unite(a, a + 1);
        a = rgt[find(a)] + 1;
    }
}

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

    cin >> N >> A[1] >> B[1] >> C[1];
    for (int i = 2; i < N; ++ 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;
    }

    init();
    for (int i = N - 1; i; -- i)
        paint(min(A[i], B[i]), max(A[i], B[i]), C[i]);

    for (int i = 1; i < N; ++ i)
        cout << color[i] << '\n';
    return 0;
}