Cod sursa(job #3190862)

Utilizator MrPuzzleDespa Fabian Stefan MrPuzzle Data 8 ianuarie 2024 10:35:24
Problema Curcubeu Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <bits/stdc++.h>

#define DIM 1000000

//#define int long long

using namespace std;

//ifstream f("in.in");
//ofstream g("out.out");

ifstream f("curcubeu.in");
ofstream g("curcubeu.out");

int n;
int a,b,c;

int len[DIM+5];
int t[DIM+5];
int v[DIM+5];
int r[DIM+5];

struct info{
    int a;
    int b;
    int c;
}q[DIM+5];

int getRoot(int x){

    if(t[x] == x){
        return x;
    }

    int rad = getRoot(t[x]);
    t[x] = rad;

    return rad;
}

void join(int x,int y){

    x = getRoot(x);
    y = getRoot(y);

    if(x != y){
        if(len[x] > len[y]){
            swap(x,y);
        }

        t[x] = y;
        if(len[x] == len[y]){
            len[y] ++;
        }
        r[y] = max(r[x],r[y]);
    }
}

signed main(){

    f>>n;
    f>>q[1].a>>q[1].b>>q[1].c;

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

    for(int i=1;i<=n-1;i++){
        t[i] = i;
        r[i] = i;
        len[i] = 1;
    }

    for(int i = n-1;i>=1;i--){
        a = q[i].a;
        b = q[i].b;
        c = q[i].c;

        if(a>b){
            swap(a,b);
        }

        //cout<<a<<" "<<b<<" "<<c<<'\n';

        for(int j=a;j<=b;j++){
            if(v[j] == 0){
                v[j] = c;

                if(v[j-1] != 0){
                    join(j,j-1);
                }

                if(v[j+1] != 0){
                    join(j,j+1);
                }
            }else{
                j = r[j];
            }
        }
    }

    for(int i=1;i<=n-1;i++){
        g<<v[i]<<"\n";
    }

    return 0;
}