Cod sursa(job #3331335)

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

using namespace std;

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

const int MAXN = 1000005;
int L[MAXN], R[MAXN], C[MAXN], Next[MAXN], sol[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() {
    ios_base::sync_with_stdio(false);
    in.tie(NULL);

    int N;
    long long A, B, C_val;
    if (!(in >> N >> A >> B >> C_val)) return 0;

    // Prima pensula (i=1) foloseste valorile citite direct
    L[1] = (int)(min(A, B) + 1);
    R[1] = (int)(max(A, B) + 1);
    C[1] = (int)C_val;

    // Generam restul de N-2 pensule (de la i=2 pana la N-1)
    for (int i = 2; i < N; i++) {
        A = (A * (i - 1)) % N;
        B = (B * (i - 1)) % N;
        C_val = (C_val * (i - 1)) % N;

        L[i] = (int)(min(A, B) + 1);
        R[i] = (int)(max(A, B) + 1);
        C[i] = (int)C_val;
    }

    // Initializare DSU
    for (int i = 1; i <= N + 1; i++) Next[i] = i;

    // Procesare INVERSA: de la ultima pensula (N-1) spre prima (1)
    for (int i = N - 1; i >= 1; i--) {
        for (int j = find_next(L[i]); j <= R[i]; j = find_next(j)) {
            if (j < N) sol[j] = C[i];
            Next[j] = find_next(j + 1);
        }
    }

    for (int i = 1; i < N; i++) {
        out << sol[i] << "\n";
    }

    return 0;
}