Cod sursa(job #3360580)

Utilizator mmateiMatei Barbu mmatei Data 14 iulie 2026 18:44:43
Problema Curcubeu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <fstream>
#include <vector>
#include <iostream>

#define int long long

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];

signed 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;
        //if(q[i].a || q[i].b || q[i].c)cout<<q[i].a<<" "<<q[i].b<<" "<<q[i].c<<"\n";
        a[i] = -1;
    }
    for(int i=n-1;i>=1;i--){
        int st=min(q[i].a,q[i].b);
        int dr=max(q[i].a,q[i].b);

        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],0LL)<<"\n";
    return 0;
}