Pagini recente » Atasamentele paginii Profil alexia.ams | Cod sursa (job #1282996) | Cod sursa (job #3311183)
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct DSU {
int n;
vector<int> a;
DSU(int N) {
n = N;
a.resize(n);
for(int i = 0; i < n; i ++) {
a[i] = i;
}
}
int leader(int x) {
if(x == a[x])
return x;
return a[x] = leader(a[x]);
}
void merge(int x, int y) {
x = leader(x);
y = leader(y);
a[x] = y;
}
};
signed main() {
freopen("curcubeu.in", "r", stdin);
freopen("curcubeu.out", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n;
vector<int> a(n - 1), b(n - 1), c(n - 1);
cin >> a[0] >> b[0] >> c[0];
for(int i = 1; i < n - 1; i ++) {
a[i] = (a[i - 1] * (i + 1)) % n;
b[i] = (b[i - 1] * (i + 1)) % n;
c[i] = (c[i - 1] * (i + 1)) % n;
}
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
reverse(c.begin(), c.end());
DSU dsu(n);
n --;
vector<int> ans(n);
for(int i = 0; i < n; i ++) {
a[i] --; b[i] --;
if(b[i] < a[i])
swap(a[i], b[i]);
for(int j = dsu.leader(a[i]); j <= b[i]; j = dsu.leader(j)) {
ans[j] = c[i];
dsu.merge(j, j + 1);
}
}
for(auto i : ans) {
cout << i << '\n';
}
}