Cod sursa(job #3325569)

Utilizator parrot279Sofi Tudose parrot279 Data 25 noiembrie 2025 19:19:46
Problema Curcubeu Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("curcubeu.in");
ofstream fout("curcubeu.out");
int radacina(int nod);

int tata[1000001], a[1000001], b[1000001], c[1000001], culoare[1000001];
stack<long long> s;

int main()
{
    int n;
    fin>>n>>a[1]>>b[1]>>c[1];
    tata[1] = 1; tata[n] = n;
    for(int i = 2; i <= n-1; ++i)
    {
        tata[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 i = n-1; i >= 1; --i)
    {
        int st = min(a[i], b[i]), dr = max(a[i], b[i]);
        if(st == 0)
            st = 1;
        for(int j = radacina(st); j <= dr; j = radacina(j))
        {
            culoare[j] = c[i];
            tata[j] = j+1;
        }
    }
    for(int i = 1; i <= n-1; ++i)
        fout<<culoare[i]<<"\n";




    return 0;
}

int radacina(int nod)
{
    int r = nod;
    while(tata[r] != r)
        r = tata[r];

    while(tata[nod] != nod)
    {
        int aux = nod;
        nod = tata[nod];
        tata[aux] = r;
    }
    return r;
}