Pagini recente » Cod sursa (job #1976427) | Arbori de intervale si aplicatii in geometria computationala | Problema satisfiabilităţii formulelor logice de ordinul doi | Cod sursa (job #3225337) | Cod sursa (job #1915372)
#include <fstream>
using namespace std;
ifstream fin ("curcubeu.in");
ofstream fout ("curcubeu.out");
inline unsigned int FATHER (unsigned int node);
inline void QUERY (unsigned int left, unsigned int right, unsigned int colour);
unsigned int N;
unsigned int A[1000001], B[1000001], C[1000001];
unsigned int tree[1000001];
unsigned int start, finish, start1;
unsigned int i, j;
unsigned int sol[1000001];
int main () /// It's a Disjoint-Set Forests' based algorithm.
{
/// READ
fin >> N >> A[1] >> B[1] >> C[1];
/// SOLVE
for (i=2; i<=N-1; i++) /// Calculate A, B and C arrays, according to the recurrence formulas.
{
A[i] = (A[i-1]*i)%N;
B[i] = (B[i-1]*i)%N;
C[i] = (C[i-1]*i)%N;
}
for (i=N-1; i>=1; i--) /// For each position of the A, B and C arrays...
{
start = min(A[i],B[i]); /// We find the start point, which is the smallest value.
finish = max(A[i],B[i]); /// We find the finish point, which is the largest value.
QUERY(start,finish,C[i]); /// We calculate the solution of the current index.
}
/// PRINT
for (i=1; i<=N-1; i++)
fout << sol[i] << '\n';
return 0;
}
inline unsigned int FATHER (unsigned int node) /// Find the father of a node.
{
if (node == tree[node]) /// If the node is also its own father...
return node; /// We just found its father.
return FATHER(tree[node]); /// Otherwise, we continue searching for it...
}
inline void QUERY (unsigned int left, unsigned int right, unsigned int colour) /// Calculate the solution.
{
while (left <= right) /// While we have not reached the end of the interval yet...
{
if (sol[left] != 0)
left = FATHER(left); /// Find the father of node left.
if (left <= right) /// If left is still smaller than right...
{
sol[left] = colour; /// Update the solution.
tree[left] = right + 1; /// Update tree.
left++; /// Increase left.
}
}
}