Cod sursa(job #3360234)

Utilizator mmateiMatei Barbu mmatei Data 10 iulie 2026 20:37:40
Problema Curcubeu Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 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;
    }
    bool root(int a){
        return rad(a);
    }
    int nxt(int a){
        return next[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=(q[i-1].a*i)%n;
        q[i].b=(q[i-1].b*i)%n;
        q[i].c=(q[i-1].c*i)%n;
        a[i]=-1;
    }
    for(int i=n-1;i>=1;i--){
        int st=min(q[i].a,q[i].b),dr=max(q[i].a,q[i].b);
        if(a[st]==-1)a[st]=q[i].c;
        for(int j=st+1;j<=dr;){
            v.join(j-1,j);
            if(a[j]==-1)a[j]=q[i].c;
            j++;
            if(v.root(j-1))j=max(v.nxt(j-1),j);

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