Cod sursa(job #3350558)

Utilizator eric_dragosDragos Eric eric_dragos Data 9 aprilie 2026 16:17:43
Problema Curcubeu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("curcubeu.in");
ofstream fout("curcubeu.out");

vector<int> root;

int find(int x){
    if(root[x] != x) root[x] = find(root[x]);
    return root[x];
}

int main(){
    long long n, A, B, C;
    fin >> n >> A >> B >> C;
    
    vector<long long> va(n), vb(n), vc(n);
    va[1]=A; vb[1]=B; vc[1]=C;
    for(int i=2; i<=n-1; i++){
        va[i] = (va[i-1] * i) % n;
        vb[i] = (vb[i-1] * i) % n;
        vc[i] = (vc[i-1] * i) % n;
    }
    
    // root[i] = prima pozitie necolorata >= i
    root.resize(n+1);
    iota(root.begin(), root.end(), 0);
    
    vector<long long> ans(n, 0);
    
    // Procesam invers
    for(int i=n-1; i>=1; i--){
        long long l = min(va[i], vb[i]);
        long long r = max(va[i], vb[i]);
        long long c = vc[i];
        
        if(l == 0) l = 1; // pozitiile sunt 1..n-1
        
        // Coloram toate necolorate din [l, r]
        int pos = find(l);
        while(pos <= r){
            ans[pos] = c;
            root[pos] = pos + 1; // marcam ca colorat
            pos = find(pos + 1);
        }
    }
    
    for(int i=1; i<=n-1; i++){
        fout << ans[i] << '\n';
    }
    return 0;
}