Pagini recente » Cod sursa (job #1837474) | Cod sursa (job #1808401) | Cod sursa (job #1024831) | Cod sursa (job #2710979) | Cod sursa (job #2193091)
#include <fstream>
#define MAX 100005
using namespace std;
ifstream fin("curcubeu.in");
ofstream fout("curcubeu.out");
int Arbore[MAX], Rank[MAX], a[MAX], b[MAX], c[MAX], culoare[MAX];
/// Union find -Start
int findR(int val){
int r = val, y;
while(Arbore[r] != r)
r = Arbore[r];
///compresia caii
while(Arbore[val] != val){
y = Arbore[val];
Arbore[val] = r;
val = y;
}
return r;
}
void Unite(int Rx, int Ry){
if(Rank[Rx] > Rank[Ry])
Arbore[Rx] = Ry;
else Arbore[Ry] = Rx;
if(Rank[Rx] == Rank[Ry])
Rank[Ry] ++;
}
/// Finish
void swap(int &A, int &B){
A ^= B;
B ^= A;
A ^= B;
}
int main()
{
int n;
fin >> n >> a[1] >> b[1] >> c[1];
for(int i = 0; i < n; ++i){
Arbore[i] = i;
Rank[i] = 1;
}
if(a[1] > b[1])
swap(a[1], b[1]);
for(int i = 2; i < n; ++i)
{
a[i] = (1LL * a[i - 1] * i) % n;
b[i] = (1LL * b[i - 1] * i) % n;
c[i] = (1LL * c[i - 1] * i) % n;
if(a[i] > b[i])
swap(a[i], b[i]);
}
for(int i = n - 1; i >= 1; --i){
int j = findR(a[i]);
while(j <= b[i] && j){
if(culoare[j] == 0){
culoare[j] = c[i];
Unite(j, b[i]);
}
j = findR(++j);
}
}
for(int i = 1; i < n; ++i)
fout << culoare[i] << '\n';
return 0;
}