Cod sursa(job #3331336)

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

using namespace std;

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

const int MAXN = 1000005;

// Folosim int pentru a economisi memorie (Limita e 64MB)
int L[MAXN], R[MAXN], Col[MAXN];
int Next[MAXN], solutie[MAXN];

int find_next(int pos) {
    int root = pos;
    while (Next[root] != root) root = Next[root];
    int aux = pos;
    while (Next[aux] != root) {
        int next_node = Next[aux];
        Next[aux] = root;
        aux = next_node;
    }
    return root;
}

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

    int N;
    long long A_curr, B_curr, C_curr;
    if (!(in >> N >> A_curr >> B_curr >> C_curr)) return 0;

    // ETAPA 1: Generarea riguroasa
    // i reprezinta indicele pensulei, de la 1 la N-1
    for (int i = 1; i < N; i++) {
        // La fiecare pas i, folosim valorile curente pentru pensula i
        L[i] = (int)(min(A_curr, B_curr) + 1);
        R[i] = (int)(max(A_curr, B_curr) + 1);
        Col[i] = (int)C_curr;

        // DUPA ce am salvat pensula i, calculam valorile pentru i + 1
        // i este chiar multiplicatorul conform formulei (A_i = A_{i-1} * i)
        A_curr = (A_curr * i) % N;
        B_curr = (B_curr * i) % N;
        C_curr = (C_curr * i) % N;
    }

    // ETAPA 2: Initializare DSU
    // Mergem pana la N+1 pentru a avea sentinela
    for (int i = 1; i <= N + 1; i++) {
        Next[i] = i;
    }

    // ETAPA 3: Procesare INVERSA (Offline)
    // Ultima pensula aplicata cronologic (N-1) e prima procesata de noi
    for (int i = N - 1; i >= 1; i--) {
        int start_pos = L[i];
        int end_pos = R[i];

        // find_next ne trimite direct la prima celula necolorata din interval
        for (int j = find_next(start_pos); j <= end_pos; j = find_next(j)) {
            // Ne intereseaza doar celulele 1...N-1 conform cerintei
            if (j < N) {
                solutie[j] = Col[i];
            }
            // "Anulam" celula j: o legam de j+1
            Next[j] = find_next(j + 1);
        }
    }

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

    return 0;
}