Pagini recente » Cod sursa (job #1780174) | Cod sursa (job #1528672) | Cod sursa (job #1997352) | Cod sursa (job #2259549) | Cod sursa (job #1618607)
#include <fstream>
#include <algorithm>
#include <stack>
#include <cstring>
using namespace std;
ifstream in("curcubeu.in");
ofstream out("curcubeu.out");
const int N = 1000010;
int n;
int f[N];
int r[N];
int _right[N];
int _final[N];
stack < int > st_a, st_b, st_c;
void _clear(int _n) {
n = _n;
for(int i = 1; i <= n; i++) {
f[i] = i;
r[i] = 1;
_right[i] = i;
}
}
int get_father(int x) {
if(x != f[x]) {
f[x] = get_father(f[x]);
}
return f[x];
}
void _merge(int x, int y) {
int root_x, root_y;
root_x = get_father(x);
root_y = get_father(y);
if(root_x != root_y) {
if(r[root_x] < r[root_y]) {
f[root_x] = root_y;
_right[root_y] = max(_right[root_y], _right[root_x]);
}
else if(r[root_x] > r[root_y]) {
f[root_y] = root_x;
_right[root_x] = max(_right[root_x], _right[root_y]);
}
else {
f[root_x] = root_y;
_right[root_y] = max(_right[root_y], _right[root_x]);
r[root_y]++;
}
}
}
int main() {
int a, b, c, i, j, start, fin;
in >> n >> a >> b >> c;
_clear(n);
st_a.push(a);
st_b.push(b);
st_c.push(c);
for(i = 2; i < n; i++) {
a = (i * a) % n;
b = (i * b) % n;
c = (i * c) % n;
st_a.push(a);
st_b.push(b);
st_c.push(c);
}
for(i = 1; i < n; i++) {
a = st_a.top();
b = st_b.top();
c = st_c.top();
st_a.pop();
st_b.pop();
st_c.pop();
start = min(a, b);
fin = max(a, b);
j = start;
while(j < fin) {
_final[j] = c;
_merge(j, j + 1);
j = _right[get_father(j)];
}
if(j == fin) {
_final[fin] = c;
}
}
for(i = 1; i < n; i++) {
out << _final[i] << '\n';
}
return 0;
}