Cod sursa(job #3190303)

Utilizator gianiferSpita Alexandru-Mihai gianifer Data 7 ianuarie 2024 14:57:30
Problema Curcubeu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <bits/stdc++.h>
#define N_MAX 1000005

using namespace std;

ifstream fin("curcubeu.in");

ofstream fout("curcubeu.out");

int tati[N_MAX], nr[N_MAX], dreapta[N_MAX];
int n, m;
int rez[N_MAX];
int getroot(int x)
{
    while (tati[x] != 0)
        x = tati[x];
    return x;
}
void join(int x, int y)
{
    x = getroot(x);
    y = getroot(y);
    if (nr[x] < nr[y])
        swap(x, y);
    tati[y] = x;
    nr[x] += nr[y];
    dreapta[x] = max(dreapta[x], dreapta[y]);
}
void solve(int op, int a, int b, int c)
{
    if ((op + 1) <= (n - 1))
    {
        solve(op + 1, 1LL * (a * (op + 1) % n), 1LL * (b * (op + 1) % n), 1LL * (c * (op + 1) % n));
    }
    for (int i = min(a, b); i <= max(a, b); i++)
    {

        if (rez[i] != 0)
        {
            i = dreapta[getroot(i)];
            continue;
        }
        if (rez[i] == 0)
        {
            rez[i] = c;
            if (rez[i - 1] != 0)
                join(rez[i - 1], rez[i]);
            else if (rez[i + 1] != 0)
                join(rez[i + 1], rez[i]);
        }
    }
}
int main()
{
    fin >> n;
    int x, y, z;
    fin >> x >> y >> z;
    for (int i = 1; i <= n - 1; i++)
    {
        nr[i] = 1;
        dreapta[i] = i;
    }
    solve(1, x, y, z);
    for (int i = 1; i <= n - 1; i++)
        fout << rez[i] << '\n';
}