Cod sursa(job #3308858)

Utilizator MihneaStoicaMihnea Teodor Stoica MihneaStoica Data 28 august 2025 19:31:28
Problema Curcubeu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<int> nxt;

int root(int x) {
    if (x >= nxt.size() || x == nxt[x])
        return x;
    return nxt[x] = root(nxt[x]);
}

signed main() {
#ifndef LOCAL
    ifstream cin("curcubeu.in");
    ofstream cout("curcubeu.out");
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    vector<tuple<int, int, int>> v(n);
    cin >> get<0>(v[1]) >> get<1>(v[1]) >> get<2>(v[1]);

    for (int i = 2; i < n; i ++) {
        v[i] = {get<0>(v[i - 1]) * i % n, 
            get<1>(v[i - 1]) * i % n, 
            get<2>(v[i - 1]) * i % n};
    }

    nxt.resize(n);
    iota(nxt.begin(), nxt.end(), 0);
    vector<int> col(n);

    for (int i = n - 1; i >= 1; i --) {
        int a = min(get<0>(v[i]), get<1>(v[i])), 
        b = max(get<0>(v[i]), get<1>(v[i])),
        c = get<2>(v[i]);

        for (int j = root(a); j <= b; j = root(j)) {
            col[j] = c;
            nxt[j] = j + 1;
        }
    }

    for (int i = 1; i < n; i ++) {
        cout << col[i] << '\n';
    }

    return 0;
}