Cod sursa(job #3316472)

Utilizator adr_grIrina S adr_gr Data 18 octombrie 2025 21:20:30
Problema Curcubeu Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <iostream>
#include <fstream>
using namespace std;

const int MAX = 1000005;

int N;
int A[MAX], B[MAX], C[MAX];
int color[MAX];
int next_free[MAX];

// Funcție care găsește următoarea căsuță necolorată
int find_next(int i) {
    if (i >= N) return N;
    if (next_free[i] == i) return i;
    next_free[i] = find_next(next_free[i]);
    return next_free[i];
}

int main() {
    ifstream in("curcubeu.in");
    ofstream out("curcubeu.out");

    int A1, B1, C1;
    in >> N >> A1 >> B1 >> C1;

    int M = N - 1;

    // Generăm toate operațiile
    A[1] = A1;
    B[1] = B1;
    C[1] = C1;

    for (int i = 2; i <= M; i++) {
        A[i] = (A[i - 1] * i) % N;
        B[i] = (B[i - 1] * i) % N;
        C[i] = (C[i - 1] * i) % N;
    }

    // Inițializăm vectorul next_free
    for (int i = 1; i <= N; i++) {
        next_free[i] = i;
    }

    // Parcurgem operațiile în ordine inversă
    for (int i = M; i >= 1; i--) {
        int st = min(A[i], B[i]);
        int dr = max(A[i], B[i]);

        if (st == 0) st = 1;
        if (dr >= N) dr = N - 1;

        int poz = find_next(st);
        while (poz <= dr) {
            color[poz] = C[i];
            next_free[poz] = poz + 1;
            poz = find_next(poz);
        }
    }

    // Afișăm culorile finale
    for (int i = 1; i < N; i++) {
        out << color[i] << '\n';
    }

    return 0;
}