Cod sursa(job #3191824)

Utilizator YosifIosif Andrei Stefan Yosif Data 10 ianuarie 2024 18:26:08
Problema Curcubeu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <bits/stdc++.h>
using namespace std;

string file = "curcubeu";
ifstream fin(file + ".in");
ofstream fout(file + ".out");

int n, A, B, C;

struct update{

    int a, b, c;
};

update p[1000001];
bool f[1000001];
int t[1000001];
int Next[1000001];
int res[1000001];

int root(int x) {

    if (x == t[x])
        return x;
    return t[x] = root(t[x]);
}

inline void unit(int x, int y) {

    x = root(x);
    y = root(y);

    if (x != y) {

        t[x] = y;
        Next[y] = max(Next[x], Next[y]);
    }
}

inline void add(int pos) {

    f[pos] = true;
    if (pos - 1 >= 1 && f[pos - 1])
        unit(pos - 1, pos);
    if (pos + 1 <= n && f[pos + 1])
        unit(pos, pos + 1);
}

int main(){

    fin >> n >> A >> B >> C;
    n--;

    for (int i = 1; i <= n; i++)
        t[i] = i, Next[i] = i + 1, f[i] = false;

    for (int i = 1; i <= n; i++) {

        p[i] = {A, B, C};

        if (p[i].a > p[i].b)
            swap(p[i].a, p[i].b);

        int A2, B2, C2;

        A2 = (1LL * (i + 1) * A) % (n + 1);
        B2 = (1LL * (i + 1) * B) % (n + 1);
        C2 = (1LL * (i + 1) * C) % (n + 1);

        A = A2;
        B = B2;
        C = C2;
    }

    for (int i = n; i >= 1; i--) {

        int k = p[i].a;

        while (k <= p[i].b) {

            if (f[k]) {

                k = Next[root(k)];
                continue;
            }

            res[k] = p[i].c;
            add(k++);
        }
    }

    for (int i = 1; i <= n; i++)
        fout << res[i] << '\n'; 

    return 0;
}