Cod sursa(job #3190853)

Utilizator MrPuzzleDespa Fabian Stefan MrPuzzle Data 8 ianuarie 2024 10:04:21
Problema Curcubeu Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.56 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;
    }

    return getRoot(t[x]);

}

void join(int x,int y){

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

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

    t[x] = y;
    len[y] += len[x];
    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 = (q[i-1].a * i)%n;
        q[i].b = (q[i-1].b * i)%n;
        q[i].c = (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;
}