Cod sursa(job #3331333)

Utilizator boboc132Boboc Teodor boboc132 Data 26 decembrie 2025 18:24:58
Problema Curcubeu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.05 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

const int MAXN = 1000005;

// Tablourile pentru stocarea datelor (Offline)
int L[MAXN], R[MAXN], C[MAXN];
int Next[MAXN], solutie[MAXN];
int N;

// Functia find_next (DSU Iterativ - Fara recursie, fara Signal 11)
int find_next(int pos) {
    int root = pos;
    // Pasul 1: Gasim radacina (prima celula necolorata)
    while (Next[root] != root) {
        root = Next[root];
    }
    
    // Pasul 2: Path Compression (Aplatizam arborele pentru viteza)
    int aux = pos;
    while (Next[aux] != root) {
        int next_node = Next[aux];
        Next[aux] = root;
        aux = next_node;
    }
    return root;
}

int main() {
    // Viteza maxima pentru I/O
    ios_base::sync_with_stdio(false);
    in.tie(NULL);

    long long Ar, Br, Cr;
    if (!(in >> N >> Ar >> Br >> Cr)) return 0;

    // ETAPA 1: Generarea si stocarea pensulelor
    for (int i = 1; i < N; i++) {
        L[i] = (int)(min(Ar, Br) + 1);
        R[i] = (int)(max(Ar, Br) + 1);
        C[i] = (int)Cr;

        // Formulele de generare pentru pasul i+1
        Ar = (Ar * (i + 1)) % N;
        Br = (Br * (i + 1)) % N;
        Cr = (Cr * (i + 1)) % N;
    }

    // ETAPA 2: Initializarea DSU
    // Fiecare celula arata spre ea insasi (e libera)
    for (int i = 1; i <= N + 1; i++) {
        Next[i] = i;
    }

    // ETAPA 3: Procesarea INVERSA (de la ultima pensula la prima)
    for (int i = N - 1; i >= 1; i--) {
        // Cautam prima pozitie libera incepand de la L[i]
        for (int j = find_next(L[i]); j <= R[i]; j = find_next(j)) {
            solutie[j] = C[i];
            
            // "Stergem" celula j unind-o cu j+1
            // De acum, oricine ajunge la j va fi trimis la find_next(j+1)
            Next[j] = find_next(j + 1);
        }
    }

    // ETAPA 4: Afisarea rezultatului
    for (int i = 1; i < N; i++) {
        out << solutie[i] << "\n";
    }

    return 0;
}