Cod sursa(job #1915379)

Utilizator tudorgalatanRoman Tudor tudorgalatan Data 8 martie 2017 20:50:26
Problema Curcubeu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 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 ()
{
    /// READ

    fin >> 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--)
    {
        start = min(A[i],B[i]);
        finish = max(A[i],B[i]);
        QUERY(start,finish,C[i]);
    }

    /// PRINT

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

    return 0;
}

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

inline 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++;
        }
    }
}