Cod sursa(job #3273540)

Utilizator BledeaAlexBledea Alexandru BledeaAlex Data 2 februarie 2025 16:24:41
Problema Curcubeu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <bits/stdc++.h>

using namespace std;

const int N_MAX = 1e6 + 5;
long long N, A, B, C;
int sol[N_MAX];

struct Query
{
    int A, B, C;

    Query() {}

    Query(int _A, int _B, int _C):
        A(_A), B(_B), C(_C) {}

};

struct DisjointSetUnion /// T[x] = urmatorul spatiu liber dupa x
{
    int T[N_MAX];
    int N;

    int FindSet(int v)
    {
        if(T[v] != v)
            T[v] = FindSet(T[v]);
        return T[v];
    }

    void UnionSet(int a, int b)
    {
        a = FindSet(a);
        b = FindSet(b);

        if(a >= b)
            return;

        T[a] = b;
    }

    void Build(int N)
    {
        this->N = N;

        for(int i = 1; i <= N + 1; i++)
            T[i] = i;
    }
} dsu;

void SetInput(string name)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    (void)!freopen((name + ".in").c_str(), "r", stdin);
    (void)!freopen((name + ".out").c_str(), "w", stdout);
}

void ReadInput()
{
    cin >> N >> A >> B >> C;
}

void Solve()
{
    stack<Query> Q;
    Q.push(Query(0, 0, 0));
    Q.push(Query(A, B, C));

    Query q;
    for(int i = 2; i < N; i++)
    {
        q = Q.top();
        Q.push(Query((1LL * q.A * i) % N, (1LL * q.B * i) % N, (1LL * q.C * i) % N));
    }

    for(int i = N - 1, st, dr, culoare; i >= 1; i--)
    {
        q = Q.top();
        Q.pop();

        st = min(q.A, q.B);
        dr = max(q.A, q.B);
        culoare = q.C;

        for(int j = dsu.FindSet(st); j <= dr; j = dsu.FindSet(j))
        {
            sol[j] = culoare;
            dsu.T[j] = j + 1;
        }
    }

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

int main()
{
    SetInput("curcubeu");

    ReadInput();
    dsu.Build(N);
    Solve();

    return 0;
}