Cod sursa(job #3331337)

Utilizator boboc132Boboc Teodor boboc132 Data 26 decembrie 2025 18:32:45
Problema Curcubeu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream fin("curcubeu.in");
ofstream fout("curcubeu.out");

int t[1000009];
int rez[1000009];
long long a[1000009], b[1000009], c[1000009];

// Varianta recursiva (daca a mers la el, merge si la noi)
int root(int x){
    if(x == t[x]) return x;
    return t[x] = root(t[x]);
}

int main(){
    int n;
    if(!(fin >> n)) return 0;

    // Initializare DSU
    for(int i = 1; i <= n + 1; i++) t[i] = i;

    // Citim prima pensula
    fin >> a[1] >> b[1] >> c[1];

    // ETAPA 1: Generarea (ATENTIE LA i-ul de aici)
    for(int i = 2; i < n; 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;
    }

    // ETAPA 2: Procesarea Inversa (de la n-1 la 1)
    for(int i = n - 1; i >= 1; i--){
        int st = min(a[i], b[i]);
        int dr = max(a[i], b[i]);

        // Celulele noastre sunt de la 1 la n-1. 
        // Daca st e 0, il urcam la 1.
        if(st == 0) st = 1;

        // DSU jump
        for(int j = root(st); j <= dr; j = root(j)){
            rez[j] = (int)c[i];
            t[j] = j + 1; // "Legam" celula de urmatoarea
        }
    }

    // ETAPA 3: Afisarea (primele n-1 celule)
    for(int i = 1; i < n; i++){
        fout << rez[i] << '\n';
    }

    return 0;
}