Pagini recente » Cod sursa (job #3361547) | Cod sursa (job #3362096) | Cod sursa (job #3362034) | Cod sursa (job #3361548) | Cod sursa (job #3361818)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("curcubeu.in");
ofstream fout("curcubeu.out");
int n;
struct query {
int st, dr, color;
query() :st(-1), dr(-1), color(0) {};
query(query& ant,int i) {
int auxSt = ((long long)ant.st * i) % n;
int auxDr = ((long long)ant.dr * i) % n;
this->st = min(auxSt,auxDr);
this->dr = max(auxSt, auxDr);
this->color= ((long long)ant.color * i) % n;
}
};
class disjuncte {
public:
vector<int>father;
vector<int>maxPoz;//pozitia maxima care este colorata pe un anumit interval
void resize(int n) {
father.resize(n, -1);
maxPoz.resize(n);
for (int i = 0; i < n; ++i) {
maxPoz[i] = i;
}
}
int getRoot(int nod) {
if (father[nod] == -1) {
return nod;
}
father[nod] = getRoot(father[nod]);
return father[nod];
}
void combin(int a,int b) {
a = getRoot(a);
b = getRoot(b);
if (a != b) {
father[b] = a;
maxPoz[a] = max(maxPoz[a], maxPoz[b]);
}
}
};
int main()
{
int a,b,c;
fin >> n>>a>>b>>c;
disjuncte forest;
forest.resize(n);
vector<int>colors(n, -1);
vector<query>q(n-1);
q[0].st = min(a, b);
q[0].dr = max(a, b);
q[0].color = c;
for (int i = 1; i < n-1; ++i) {
q[i] = query(q[i - 1], i + 1);
}
for (int i = n - 2; i >= 0; --i) {
int poz = forest.getRoot(q[i].st);
int startSecv = -1;
while (poz<=q[i].dr)
{
if (colors[poz]==-1) {//le unim cu multimea inceputului secventei
colors[poz] = q[i].color;
if (startSecv ==-1) {
startSecv = poz;
}
else {
forest.combin(startSecv, poz);
}
}
else {//sarim peste toate din aceasta multime
if (startSecv!=-1) {//vrem sa le combinam cu multimea anterioara ca sa sarim mai mult daca mai vine un query (sper)
forest.combin(startSecv, poz);
}
poz = forest.maxPoz[poz];
startSecv = -1;
}
++poz;
}
}
for (int i = 1; i < n; ++i) {
fout << colors[i] << "\n";
}
return 0;
}
//=^..^=