Pagini recente » Cod sursa (job #2128524) | Cod sursa (job #1480882) | Cod sursa (job #1474470) | Cod sursa (job #1835172) | Cod sursa (job #2811029)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("curcubeu.in");
ofstream fout("curcubeu.out");
const int kN = 1e6;
int a[kN], b[kN], c[kN], sol[kN];
bitset<1 + kN> vis;
struct DSU {
vector<int> p, sz;
DSU(int n) {
p.resize(n + 1);
iota(p.begin(), p.end(), 0);
sz.assign(n + 1, 1);
}
int root(int x) {
if (x == p[x]) {
return x;
}
return p[x] = root(p[x]);
}
bool unite(int u, int v) {
int x = root(u), y = root(v);
if (x == y) {
return false;
}
if (sz[x] > sz[y]) {
swap(x, y);
}
p[x] = y;
sz[y] += sz[x];
return true;
}
int getNext(int x) {
return x + sz[root(x)];
}
};
void testCase() {
int n;
fin >> n >> a[1] >> b[1] >> c[1];
for (int i = 2; i < n; ++i) {
a[i] = (int64_t)a[i - 1] * i % n;
b[i] = (int64_t)b[i - 1] * i % n;
c[i] = (int64_t)c[i - 1] * i % n;
}
DSU t(n);
for (int i = n - 1; i > 0; --i) {
int l = min(a[i], b[i]), r = max(a[i], b[i]);
if (l == 0) {
l = 1;
}
if (vis[l]) {
l = t.getNext(l);
}
while (l <= r) {
vis[l] = true;
sol[l] = c[i];
if (1 < l && vis[l - 1]) {
t.unite(l - 1, l);
}
if (l + 1 < n - 1 && vis[l + 1]) {
t.unite(l, l + 1);
}
l = t.getNext(l);
}
}
for (int i = 1; i < n; ++i) {
fout << sol[i] << '\n';
}
}
int main() {
int tests = 1;
for (int tc = 1; tc <= tests; ++tc) {
testCase();
}
fin.close();
fout.close();
return 0;
}