Cod sursa(job #2224842)

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

using namespace std;

class OutputWriter {
public:
    OutputWriter(const char *output_file) {
        out = fopen(output_file, "w");
        cursor = 0;
    }
    ~OutputWriter() { flush(); }
    OutputWriter& operator<<(int nr) {
        char digits[10];
        int cnt = 0;

        do {
            digits[cnt ++] = (nr % 10 + '0');
            nr /= 10;
        } while (nr);

        for (int i = cnt - 1; i >= 0; -- i)
            (*this) << digits[i];
        return (*this);
    }
    OutputWriter& operator<<(const char &ch) {
        if (cursor == SIZE)
            flush();
        buffer[cursor ++] = ch;
        return (*this);
    }
    void flush() {
        fwrite(buffer, 1, cursor, out);
        cursor = 0;
    }
private:
    FILE *out;
    static const int SIZE = (1 << 17);
    char buffer[SIZE];
    int cursor;
};

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");
    OutputWriter 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;
}