Pagini recente » Cod sursa (job #1066630) | Cod sursa (job #1884633) | Cod sursa (job #3349918) | Cod sursa (job #973107) | Cod sursa (job #3324859)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("curcubeu.in");
ofstream fout("curcubeu.out");
int t[1000009];
int root(int x){
if (t[x] == x) return x;
return t[x] = root(t[x]); // proper path compression
}
int main(){
int n;
fin >> n;
// initialize DSU
for (int i = 1; i <= n; i++)
t[i] = i;
vector<int> a(n+1), b(n+1), c(n+1), rez(n+1);
fin >> a[1] >> b[1] >> c[1];
// generate arrays
for (int 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;
}
// process intervals backwards
for (int i = n - 1; i >= 1; i--){
int st = min(a[i], b[i]);
int dr = max(a[i], b[i]);
st++; dr++; // shift to 1-based (if needed)
int pos = root(st);
while (pos <= dr){
rez[pos] = c[i];
t[pos] = pos + 1; // union with next
pos = root(pos);
}
}
for (int i = 1; i < n; i++)
fout << rez[i] << "\n";
return 0;
}