Cod sursa(job #1915207)

Utilizator tudorgalatanRoman Tudor tudorgalatan Data 8 martie 2017 20:10:15
Problema Curcubeu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
#include <cstdio>
#include <algorithm>

using namespace std;

unsigned int N;
unsigned int A[1000000], B[1000000], C[1000000];

unsigned int tree[1000000];
unsigned int start, finish;
unsigned int i, j;

unsigned int sol[1000000];

int main ()                                         /// It's a Disjoint-Set Forests' based algorithm.
{
    /// READ

    freopen("curcubeu.in","r",stdin);
    freopen("curcubeu.out","w",stdout);
    scanf("%d %d %d %d", &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=1; i<=N-1; 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 TEST

    /*
    printf("%d\n", N);
    for (i=1; i<=N; i++)
        printf("%d ", A[i]);
    printf("\n");
    for (i=1; i<=N; i++)
        printf("%d ", B[i]);
    printf("\n");
    for (i=1; i<=N; i++)
        printf("%d ", C[i]);
    printf("\n");
    for (i=1; i<=N; i++)
        printf("%d ", sol[i]);
    printf("\n");
    */

    /// PRINT

    for (i=1; i<=N-1; i++)
        printf("%d\n", sol[i]);

    return 0;
}