Cod sursa(job #3361969)

Utilizator Andrei_GAndreiG Andrei_G Data 31 iulie 2026 01:11:45
Problema Curcubeu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <iostream>
#pragma GCC optimize("O3,unroll-loops")
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <iomanip>
#include <numeric>
#include <cstdio>
#include <bitset>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#define int long long
//#define int short
using namespace std;

const int nmax = 1e6;

int n, a, b, c, rez[nmax + 5];

struct Node{
    int state;
    int parent;
    int next;
    int prev;
}v[nmax + 5];

class dsu{
public:
    dsu(){
        build();
    }

    int findset(int i){
        if (v[i].parent == i){
            return i;
        }
        return v[i].parent = findset(v[i].parent);
    }

    void unionsets(int i, int j){
        i = findset(i);
        j = findset(j);
        if (v[j].state){
            v[i].parent = j;
        }
        v[v[i].prev].next = v[i].next;
        v[v[i].next].prev = v[i].prev;
    }

private:
    void build(){
        for (int i = 1; i < n; i++){
            v[i] = {0, i, i + 1, i - 1};
        }
    }
};

struct query{
    int l;
    int r;
    int col;
    int idx;
}q[nmax + 5];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("curcubeu.in", "r", stdin);
    freopen("curcubeu.out", "w", stdout);
    cin>>n>>a>>b>>c;
    q[1] = {a, b, c, 1};
    for (int i = 2; i < n; i++){
        a = (a * i) % n;
        b = (b * i) % n;
        c = (c * i) % n;
        q[i] = {a, b, c, i};
    }
    dsu forest = dsu();
    for (int i = n - 1; i >= 1; i--){
        int curr = q[i].l;
        if (v[curr].state){
            curr = v[curr].next;
        }
        while (curr <= q[i].r){
            rez[curr] = q[i].col;
            v[curr].state = 1;
            forest.unionsets(curr, curr - 1);
            forest.unionsets(curr, curr + 1);
            curr = v[curr].next;
        }
    }
    for (int i = 1; i <= n - 1; i++){
        cout<<rez[i]<<"\n";
    }
}