Pagini recente » Cod sursa (job #1934352) | Cod sursa (job #2618068) | Cod sursa (job #2326960) | Cod sursa (job #236105) | Cod sursa (job #3167226)
#include <fstream>
#define ll long long
using namespace std;
ifstream cin("curcubeu.in");
ofstream cout("curcubeu.out");
const int NMAX = 1e6;
struct Query
{
int A, B, C;
}queries[NMAX + 1];
int n;
pair<int, int> T[NMAX + 1];
int Next[NMAX + 1];
int GetRoot(int node)
{
int aux = node;
while(T[node].first > 0)
node = T[node].first;
int root = node;
node = aux;
while(node != root)
{
aux = T[node].first;
T[node].first = root;
node = aux;
}
return root;
}
void Join(int x, int y, int C)
{
int rootX = GetRoot(x);
int rootY = GetRoot(y);
if(rootX == rootY)
return;
if(-T[rootX].first < -T[rootY].first)
swap(rootX, rootY);
T[rootX].first += T[rootY].first;
T[rootY].first = rootX;
Next[rootX] = max(Next[rootX], Next[rootY]);
T[rootX].second = C;
}
int main()
{
cin >> n >> queries[1].A >> queries[1].B >> queries[1].C;
for(int i = 2; i <= n - 1; i++)
{
queries[i].A = ((ll) queries[i - 1].A * i) % n;
queries[i].B = ((ll) queries[i - 1].B * i) % n;
queries[i].C = ((ll) queries[i - 1].C * i) % n;
}
for(int i = 1; i <= n - 1; i++)
{
T[i] = {-1, 0};
Next[i] = i + 1;
}
for(int i = n - 1; i >= 1; i--)
{
int x = min(queries[i].A, queries[i].B);
int y = max(queries[i].A, queries[i].B);
int C = queries[i].C;
while(x <= y && T[GetRoot(x)].second != 0)
x = Next[GetRoot(x)];
if(x <= y)
{
T[GetRoot(x)].second = C;
int connectNode = x;
while(x <= y)
{
if(T[GetRoot(x)].second == 0)
Join(connectNode, x, C);
x = Next[GetRoot(x)];
}
}
}
for(int i = 1; i <= n - 1; i++)
cout << T[GetRoot(i)].second << '\n';
return 0;
}