Pagini recente » Cod sursa (job #361170) | Cod sursa (job #1355432) | Cod sursa (job #1991889) | Cod sursa (job #81472) | Cod sursa (job #3190448)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e6+2;
int n,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]);
}
};
int 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;
}