Pagini recente » Cod sursa (job #2371067) | Cod sursa (job #719463) | Cod sursa (job #2792477) | Cod sursa (job #107475) | Cod sursa (job #2577214)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("curcubeu.in");
ofstream fout("curcubeu.out");
struct Query {
int a, b, c;
Query(int a, int b, int c) :
a(a), b(b), c(c) { }
};
class Forest {
private:
vector<int> height;
vector<int> father;
vector<int> nxtPos;
public:
Forest(int n) :
height(n + 1),
father(n + 1),
nxtPos(n + 1) {
for (int i = 1; i <= n; i++)
nxtPos[i] = i;
}
int find(int x) {
int root = x;
while (father[root])
root = father[root];
int aux;
while (father[x]) {
aux = father[x];
father[x] = root;
x = aux;
}
return root;
}
int query(int x) {
return nxtPos[find(x)];
}
void unite(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY)
return;
if (height[rootX] < height[rootY])
father[rootX] = rootY;
else {
father[rootY] = rootX;
nxtPos[rootX] = nxtPos[rootY];
if (height[rootX] == height[rootY])
height[rootX]++;
}
}
};
int main() {
int n, a, b, c; fin >> n >> a >> b >> c;
vector<Query> qry; qry.reserve(n - 1);
for (int i = 2; i <= n; i++) {
qry.emplace_back(a, b, c);
a = 1LL * a * i % n;
b = 1LL * b * i % n;
c = 1LL * c * i % n;
}
Forest dsu(n);
vector<int> ans(n);
for (int i = n - 2; i >= 0; i--)
for (int x = dsu.query(min(qry[i].a, qry[i].b)); x <= max(qry[i].a, qry[i].b); x = dsu.query(x)) {
ans[x] = qry[i].c;
dsu.unite(x, x + 1);
}
for (int i = 1; i < n; i++)
fout << ans[i] << '\n';
fout.close();
return 0;
}