Cod sursa(job #2928644)

Utilizator cyg_dawidDavid Ghiberdic cyg_dawid Data 23 octombrie 2022 16:02:57
Problema Curcubeu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <fstream>
#include <vector>
#include <algorithm>

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

typedef long long ll;

int const nmax = 1e6;
int color[nmax + 5];
int nextFree[nmax + 5];

struct query {
    int l, r, c;
};

std::vector<query> queries;

int main() {
    int n;
    fin >> n;
    int a, b, c;
    fin >> a >> b >> c;
    queries.push_back({std::max(1, std::min(a, b)), std::max(1, std::max(a, b)), c});
    for (int i = 2; i < n; i++) {
        a = ((ll)a * i) % n;
        b = ((ll)b * i) % n;
        c = ((ll)c * i) % n;
        queries.push_back({std::max(1, std::min(a, b)), std::max(1, std::max(a, b)), c});
    }
    for (int step = n - 2; step >= 0; step--) {
        int currPoz = queries[step].l;
        while (currPoz <= queries[step].r) {
            if (color[currPoz] == 0) {
                color[currPoz] = queries[step].c;
                nextFree[currPoz] = queries[step].r + 1;
                currPoz++;
            } else
                currPoz = nextFree[currPoz];
        }
    }
    for (int i = 1; i < n; i++)
        fout << color[i] << "\n";
    return 0;
}