Cod sursa(job #3190484)

Utilizator gianiferSpita Alexandru-Mihai gianifer Data 7 ianuarie 2024 17:26:15
Problema Curcubeu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 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], a[N_MAX], b[N_MAX], c[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]);
}
int main()
{
    fin >> n>>a[1] >> b[1] >> c[1];
    nr[1] = 1;
    dreapta[1] = 1;
    for (int i = 2; i <= n - 1; i++)
    {
        nr[i] = 1;
        dreapta[i] = i;
        a[i] = ((1LL * a[i - 1] * i) % n);
        b[i] = ((1LL * b[i - 1] * i) % n);
        c[i] = ((1LL * c[i - 1] * i) % n);
    }
    for (int j = n - 1; j >= 1; j--)
    {
        for (int i = min(a[j], b[j]); i <=max(a[j], b[j]); i++)
        {
            if (rez[i] != 0)
            {
                i = dreapta[getroot(i)];
            }
            else if (rez[i] == 0)
            {
                rez[i] = c[j];
                if (rez[i - 1] != 0)
                    join(i-1, i);
                else if (rez[i - 1] != 0)
                    join(i, i+1);
            }
        }
    }
    for (int i = 1; i <= n - 1; i++)
        fout << rez[i] << '\n';
}