Mai intai trebuie sa te autentifici.

Cod sursa(job #3373645)

Utilizator ciupitunicolasCiupitu Nicolas ciupitunicolas Data 7 noiembrie 2026 14:14:51
Problema Curcubeu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream cin("curcubeu.in");
ofstream cout("curcubeu.out");

int rez[1000005];

struct Paduri{
    vector<int> padre;
    Paduri(int n){
        padre.resize(n+2, -1);
    }
    int rad(int a){
        if(padre[a] == -1)
            return a;
        else{
            padre[a] = rad(padre[a]);
            return padre[a];
        }
    }
    void join(int a, int b){
        a = rad(a);
        b = rad(b);
        if(a == b) return;
        padre[a] = b;
    }
};

struct ura{
    int st, dr, culoare;
};

ura op[1000005];

int main()
{
    int n, m, a, b, c;
    cin >> n;
    m = n-1;
    Paduri dsu(n);
    cin >> a >> b >> c;
    m--;
    if(a > b)
        swap(a, b);
    op[m].st = a;
    op[m].dr = b;
    op[m].culoare = c;
    while(m--){
        a = (1LL*a*(n-1-m))%n;
        b = (1LL*b*(n-1-m))%n;
        c = (1LL*c*(n-1-m))%n;
        if(a > b)
            swap(a, b);
        op[m].st = a;
        op[m].dr = b;
        op[m].culoare = c;
    }
    m = n-1;
    for(int i = 0; i < m; i++){
        a = op[i].st;
        b = op[i].dr;
        c = op[i].culoare;
        while(a <= b){
            a = dsu.rad(a);
            if(a > b)
                break;
            dsu.join(a, a+1);
            rez[a] = c;
        }
    }
    for(int i = 1; i <= n-1; i++)
        cout << rez[i] << '\n';
    return 0;
}