Cod sursa(job #3324859)

Utilizator TeodoRazvanStancu Teodor-Razvan TeodoRazvan Data 23 noiembrie 2025 20:07:12
Problema Curcubeu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <bits/stdc++.h>
using namespace std;

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

int t[1000009];

int root(int x){
    if (t[x] == x) return x;
    return t[x] = root(t[x]);   // proper path compression
}

int main(){
    int n;
    fin >> n;

    // initialize DSU
    for (int i = 1; i <= n; i++)
        t[i] = i;

    vector<int> a(n+1), b(n+1), c(n+1), rez(n+1);

    fin >> a[1] >> b[1] >> c[1];

    // generate arrays
    for (int i = 2; i < n; 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;
    }

    // process intervals backwards
    for (int i = n - 1; i >= 1; i--){
        int st = min(a[i], b[i]);
        int dr = max(a[i], b[i]);

        st++; dr++; // shift to 1-based (if needed)

        int pos = root(st);
        while (pos <= dr){
            rez[pos] = c[i];
            t[pos] = pos + 1;  // union with next
            pos = root(pos);
        }
    }

    for (int i = 1; i < n; i++)
        fout << rez[i] << "\n";

    return 0;
}