Cod sursa(job #3316470)

Utilizator adr_grIrina S adr_gr Data 18 octombrie 2025 21:15:00
Problema Curcubeu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 1'000'005;

int N, A1, B1, C1;
int A[MAXN], B[MAXN], C[MAXN];
int color[MAXN];
int next_free[MAXN];

// Funcție care returnează următoarea poziție necolorată începând de la x
int find_next(int x) {
    if (next_free[x] == x) return x;
    return next_free[x] = find_next(next_free[x]); // compresie de drum
}

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

    fin >> N >> A1 >> B1 >> C1;

    int M = N - 1;

    // Inițializăm vectorii A, B, C
    A[1] = A1;
    B[1] = B1;
    C[1] = C1;

    for (int i = 2; i <= M; ++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;
    }

    // Inițial, fiecare poziție este propria "următoare liberă"
    for (int i = 0; i <= M; ++i)
        next_free[i] = i;

    // Procesăm 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]);

        // Căutăm prima poziție necolorată în interval
        int pos = find_next(st);
        while (pos <= dr) {
            color[pos] = C[i];              // colorăm
            next_free[pos] = pos + 1;       // marcăm că e colorată
            pos = find_next(pos);           // sărim la următoarea necolorată
        }
    }

    // Afișăm culorile căsuțelor de la 1 la N-1
    for (int i = 1; i < N; ++i)
        fout << color[i] << '\n';

    return 0;
}