Cod sursa(job #3360578)

Utilizator livliviLivia Magureanu livlivi Data 14 iulie 2026 18:33:13
Problema Curcubeu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <fstream>
#include <vector>
#include <iostream>

using namespace std;

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

int n, a[1000005];

struct rb {
    vector<int> next;
    rb(int n){
        next.resize(n + 1);
    }

    int rad(int a){
        if (next[a] == 0) return a;
        next[a] = rad(next[a]);
        return next[a];
    }
    void join(int a, int b){
        a = rad(a);
        b = rad(b);
        if (a != b) next[a] = b;
    }
    int nxt(int a){
        return max(next[a], a);
    }
};

struct query {
    int a, b, c;
} q[1000005];

int main()
{
    fin >> n >> q[1].a >> q[1].b >> q[1].c;
    a[1] = -1;
    rb v(n);
    for (int i = 2; i < n; i++){
        q[i].a = (1LL * q[i - 1].a * i) % n;
        q[i].b = (1LL * q[i - 1].b * i) % n;
        q[i].c = (1LL * q[i - 1].c * i) % n;
        a[i] = -1;
    }
    for (int i = n - 1; i >= 1; i--){
        // cerr << i << endl;
        int st = min(q[i].a, q[i].b);
        int dr = max(q[i].a, q[i].b);
        // cerr << "  " << st << " " << dr << endl;

        for(int j = st; j <= dr; j++){
            if (j > 1 && a[j - 1] != -1) {
                v.join(j - 1, j);
            }
            if (j < n - 1 && a[j + 1] != -1) {
                v.join(j, j + 1);
            }

            if(a[j] == -1) { 
                a[j] = q[i].c;
            } else {
                j = v.nxt(j);
            }

        }
    }
    for (int i = 1; i < n; i++)
        fout << max(a[i], 0) << "\n";
    return 0;
}