Cod sursa(job #2964709)

Utilizator rastervcrastervc rastervc Data 13 ianuarie 2023 18:24:39
Problema Curcubeu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
#include <iostream>

std::ifstream fin("curcubeu.in");
std::ofstream fout("curcubeu.out");

constexpr std::size_t LIM = 1e6 + 1;
int N, A[LIM], B[LIM], C[LIM], i, j;
int next[LIM], color[LIM];

static inline int find_next(int pos) {
    int aux = pos;
    while (next[pos] != pos)
        pos = next[pos];
    int result = pos;
    pos = aux;
    while (next[pos] != result) {
        aux = next[pos];
        next[pos] = result;
        pos = aux;
    }
    return result;
}

int main() {
    fin >> N >> A[1] >> B[1] >> C[1];
    if (A[1] > B[1]) std::swap(A[1], B[1]);

    next[1] = 1;
    for (i = 2; i < N; ++i) {
        A[i] = (1LL * A[i - 1] * i) % N;
        B[i] = (1LL * B[i - 1] * i) % N;
        if (A[i] > B[i]) std::swap(A[i], B[i]);
        C[i] = (1LL * C[i - 1] * i) % N;
        next[i] = i;
    }
    next[N] = N;

    for (i = N - 1; i >= 1; --i) {
        for (j = find_next(A[i]); j <= B[i]; j = next[j]) {
            color[j] = C[i];
            next[j] = find_next(j + 1);
        }
    }

    for (i = 1; i <= N - 1; ++i)
        fout << color[i] << '\n';

    fin.close();
    fout.close();
    return 0;
}