Cod sursa(job #3190453)

Utilizator divadddDavid Curca divaddd Data 7 ianuarie 2024 17:00:04
Problema Curcubeu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int NMAX = 1e6+2;
int n;
ll a[NMAX],b[NMAX],c[NMAX];
int v[NMAX];

ifstream fin("curcubeu.in");
ofstream fout("curcubeu.out");

struct DSU {
    int n;
    vector<int> t, sz, mx;
    DSU(int _n){
        n = _n;
        t.resize(n+1);
        sz.resize(n+1);
        mx.resize(n+1);
        for(int i = 1; i <= n; i++){
            t[i] = i;
            mx[i] = i;
            sz[i] = 1;
        }
    }
    int root(int nod){
        if(t[nod] == nod){
            return nod;
        }
        return t[nod] = root(t[nod]);
    }
    void join(int x, int y){
        x = root(x);
        y = root(y);
        if(sz[x] < sz[y]){
            swap(x, y);
        }
        t[y] = x;
        mx[y] = max(mx[y], mx[x]);
    }
};

signed main()
{
    fin >> n >> a[1] >> b[1] >> c[1];
    for(int i = 2; i < n; i++){
        a[i] = (a[i-1]*i)%n;
        b[i] = (b[i-1]*i)%n;
        c[i] = (c[i-1]*i)%n;
    }
    DSU nxt(n);
    for(int i = n-1; i >= 1; i--){
        int l = min(a[i], b[i]), r = max(a[i], b[i]);
        while(l <= r){
            if(v[l] == 0){
                v[l] = c[i];
                if(v[l] == v[l-1]){
                    nxt.join(l, l-1);
                }
                l++;
            }else{
                l = nxt.mx[nxt.root(l)]+1;
            }
        }
    }
    for(int i = 1; i < n; i++){
        fout << v[i] << "\n";
    }
    return 0;
}