Cod sursa(job #3324876)

Utilizator Radu_MocanasuMocanasu Radu Radu_Mocanasu Data 23 noiembrie 2025 20:53:38
Problema Curcubeu Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int a[1000005];
int b[1000005];
int c[1000005];
int v[1000005];

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

struct DSU{

    int n;

    vector <int> t;
    vector <int> sz;
    vector <int> mx;

    DSU() {}
    void _assign(int _n) {
        n = _n;
        for (int i = 0; i < n; i++) {
            t.push_back(i);
            mx.push_back(i);
        }
        sz.resize(n, 1);
    }

    int findr(int x) {
        int r = x;
        while (r != t[r]) r = t[r];
        while (x != r) {
            int y = t[x];
            t[x] = r;
            x = y;
        }
        return r;
    }

    int dsu(int x, int y) {
        int rx = findr(x), ry = findr(y);
        if (rx == ry) return 0;
        if (sz[rx] < sz[ry]) swap(rx, ry);
        t[ry] = rx;
        sz[rx] += sz[ry];
        mx[rx] = max(mx[rx], mx[ry]);
        return 1;
    }
};

DSU dsu;

int main()
{
    int n, i, t, d;
    fin >> n >> a[1] >> b[1] >> c[1];
    for (i = 2; i < n; i++) {
        a[i] = (1LL * a[i - 1] * i) % n;
        b[i] = (1LL * b[i - 1] * i) % n;
        c[i] = (1LL * c[i - 1] * i) % n;
    }
    dsu._assign(n + 5);
    for (i = n - 1; i >= 1; i--) {
        int st = min(a[i], b[i]);
        if (!st) st++;
        int dr = max(a[i], b[i]);
        int last = -1;
        for (int j = st; j <= dr; j++) {
            if (dsu.findr(j) == j) v[j] = c[i];
            if (last != -1) dsu.dsu(j, last);
            j = dsu.mx[dsu.findr(j)];
            last = j;
        }
    }
    for (i = 1; i < n; i++) fout << v[i] << "\n";
    return 0;
}