Cod sursa(job #3316471)

Utilizator adr_grIrina S adr_gr Data 18 octombrie 2025 21:17:56
Problema Curcubeu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 1000005;

int N;
int A[MAXN], B[MAXN], Cc[MAXN];
int color[MAXN];
int next_free[MAXN];

int find_next(int x) {
    if (x >= N) return N;
    if (next_free[x] == x) return x;
    return next_free[x] = find_next(next_free[x]);
}

int main() {
    freopen("curcubeu.in", "r", stdin);
    freopen("curcubeu.out", "w", stdout);

    int A1, B1, C1;
    scanf("%d%d%d%d", &N, &A1, &B1, &C1);

    int M = N - 1;
    A[1] = A1;
    B[1] = B1;
    Cc[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;
        Cc[i] = (1LL * Cc[i - 1] * i) % N;
    }

    for (int i = 1; i <= N; ++i)
        next_free[i] = i;

    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 > M) dr = M;

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

    for (int i = 1; i <= M; ++i)
        printf("%d\n", color[i]);

    return 0;
}