Pagini recente » Cod sursa (job #414515) | Cod sursa (job #1283527) | Cod sursa (job #2621045) | Cod sursa (job #1753847) | Cod sursa (job #1915244)
#include <fstream>
using namespace std;
ifstream fin ("curcubeu.in");
ofstream fout ("curcubeu.out");
unsigned int N;
unsigned int A[1000001], B[1000001], C[1000001];
unsigned int tree[1000001];
unsigned int start, finish;
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; 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=1; i<=N; i++) /// Initialize the tree.
tree[i] = 1;
for (i=N-1; i>=1; i--) /// Start the algorithm from the end to the start.
{
start = min(A[i],B[i]); /// Start is the smallest value.
finish = max(A[i],B[i]); /// Finish is the largest value.
while (start <= finish) /// While we have not reached the end of the interval...
if (start == tree[start]) /// If the start node is also its own father...
{
sol[start] = C[i]; /// Solution of index start is the value of C, according to the problem's given information.
tree[start] = finish + 1; /// Update the tree.
start++;
}
else /// Else...
{
tree[start] = finish + 1; /// Update the tree.
start = tree[start]; /// We update the start point, so we'll start from it's father.
}
}
/// PRINT
for (i=1; i<=N-1; i++)
fout << sol[i] << '\n';
return 0;
}