Pagini recente » Cod sursa (job #2047835) | Cod sursa (job #245594) | Cod sursa (job #1199863) | Cod sursa (job #1685409) | Cod sursa (job #2811032)
#include <bits/stdc++.h>
using namespace std;
class OutParser {
private:
FILE *fout;
char *buff;
int sp;
void write_ch(char ch) {
if (sp == 50000) {
fwrite(buff, 1, 50000, fout);
sp = 0;
buff[sp++] = ch;
} else {
buff[sp++] = ch;
}
}
public:
OutParser(const char* name) {
fout = fopen(name, "w");
buff = new char[50000]();
sp = 0;
}
~OutParser() {
fwrite(buff, 1, sp, fout);
fclose(fout);
}
OutParser& operator << (int vu32) {
if (vu32 <= 9) {
write_ch(vu32 + '0');
} else {
(*this) << (vu32 / 10);
write_ch(vu32 % 10 + '0');
}
return *this;
}
OutParser& operator << (long long vu64) {
if (vu64 <= 9) {
write_ch(vu64 + '0');
} else {
(*this) << (vu64 / 10);
write_ch(vu64 % 10 + '0');
}
return *this;
}
OutParser& operator << (char ch) {
write_ch(ch);
return *this;
}
OutParser& operator << (const char *ch) {
while (*ch) {
write_ch(*ch);
++ch;
}
return *this;
}
};
ifstream fin("curcubeu.in");
OutParser fout("curcubeu.out");
const int kN = 1e6;
int a[kN], b[kN], c[kN], sol[kN];
bitset<kN> vis;
void minSelf(int &x, const int &y) {
if (y < x) {
x = y;
}
}
struct DSU {
vector<int> p, start, sz;
DSU(int n) {
p.resize(n);
iota(p.begin(), p.end(), 0);
start = p;
sz.assign(n, 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];
minSelf(start[y], start[x]);
return true;
}
int getNext(int x) {
int rep = root(x);
return start[rep] + sz[rep];
}
};
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();
return 0;
}