Pagini recente » Cod sursa (job #3366866) | Cod sursa (job #3365553) | Cod sursa (job #3365956) | Autentificare | Cod sursa (job #3367912)
#include <iostream>
#include <fstream>
#include <stdint.h>
const int32_t MAX_N = 1000000;
int32_t min(int32_t x, int32_t y) {
return (x < y) ? x : y;
}
int32_t max(int32_t x, int32_t y) {
return (x > y) ? x : y;
}
struct Update {
int32_t left, right;
int32_t color;
};
struct DSF {
struct Node {
int32_t parent;
int32_t color;
int32_t next;
};
int32_t n;
Node nodes[MAX_N];
void Init(int32_t n) {
this->n = n;
for(int32_t i = 0; i != n; ++i) {
nodes[i].parent = -1;
nodes[i].color = 0;
nodes[i].next = i + 1;
}
}
int32_t GetRoot(int32_t node) {
if(nodes[node].parent == -1)
return node;
int32_t root = GetRoot(nodes[node].parent);
nodes[node].parent = root;
return root;
}
int32_t Merge(int32_t root1, int32_t root2) {
nodes[root1].parent = root2;
return root2;
}
};
int32_t n;
Update updates[MAX_N];
DSF dsf;
void GenUpdates(std::istream& fin) {
int32_t a, b, c;
fin >> n >> a >> b >> c;
for(int32_t i = 0; i != n; ++i) {
updates[i].left = min(a, b);
updates[i].right = max(a, b);
updates[i].color = c;
a = ((int64_t)a * (i + 2)) % n;
b = ((int64_t)b * (i + 2)) % n;
c = ((int64_t)c * (i + 2)) % n;
}
}
void AssignColors() {
for(int32_t i = n - 1; i != -1; --i) {
int32_t ind = updates[i].left;
int32_t root = dsf.GetRoot(ind);
if(dsf.nodes[root].color == 0)
dsf.nodes[root].color = updates[i].color;
ind = dsf.nodes[root].next;
for(; ind <= updates[i].right; ind = dsf.nodes[root].next) {
int32_t newRoot = dsf.GetRoot(ind);
if(dsf.nodes[newRoot].color == 0)
dsf.nodes[newRoot].color = updates[i].color;
root = dsf.Merge(root, newRoot);
}
}
}
void OutputRes(std::ostream& fout) {
for(int32_t i = 1; i != n; ++i)
fout << dsf.nodes[i].color << '\n';
}
int main() {
std::ifstream fin("curcubeu.in");
std::ofstream fout("curcubeu.out");
GenUpdates(fin);
dsf.Init(n);
AssignColors();
OutputRes(fout);
fin.close();
fout.close();
return 0;
}