Cod sursa(job #1915453)

Utilizator tudorgalatanRoman Tudor tudorgalatan Data 8 martie 2017 21:04:44
Problema Curcubeu Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <cstdio>
#include <algorithm>

using namespace std;

unsigned int FATHER (unsigned int node);
void QUERY (unsigned int left, unsigned int right, unsigned int colour);

unsigned int N;
unsigned long long int A[1000001], B[1000001], C[1000001];

unsigned long long int tree[1000001];
unsigned int i;

unsigned long long int sol[1000001];

int main ()
{
    /// 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++)
    {
        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--)
    {
        if (A[i] > B[i])
            swap(A[i],B[i]);
        QUERY(A[i],B[i],C[i]);
    }

    /// PRINT

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

    return 0;
}

unsigned int FATHER (unsigned int node)
{
    if (tree[node] == 0)
        return node;
    tree[node] = FATHER(tree[node]);
    return tree[node];
}

void QUERY (unsigned int left, unsigned int right, unsigned int colour)
{
    while (left <= right)
    {
        if (sol[left] != 0)
            left = FATHER(left);
        if (left <= right)
        {
            sol[left] = colour;
            tree[left] = right + 1;
            left++;
        }
    }
}