Cod sursa(job #1915221)

Utilizator tudorgalatanRoman Tudor tudorgalatan Data 8 martie 2017 20:14:07
Problema Curcubeu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#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.
            }
            else                                    /// Else...
            {
                start = tree[start];                /// We update the start point, so we'll start from it's father.
                tree[start] = finish + 1;           /// Update the tree.
            }
    }

    /// PRINT

    for (i=1; i<=N-1; i++)
        fout << sol[i] << '\n';

    return 0;
}