Cod sursa(job #1915372)

Utilizator tudorgalatanRoman Tudor tudorgalatan Data 8 martie 2017 20:48:34
Problema Curcubeu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.28 kb
#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.
        }
    }
}