Cod sursa(job #2567677)

Utilizator Teo_1101Mititelu Teodor Teo_1101 Data 3 martie 2020 18:20:42
Problema Curcubeu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1000005;

ifstream fin("curcubeu.in");
ofstream fout("curcubeu.out");

int N, A, B, C;

struct culoare
{
    int s,d,c;
};

vector < culoare > V;
culoare K;

int m[NMAX];
int sz[NMAX];
int D[NMAX];

int S[NMAX];

void Read(){

    fin >> N >> A >> B >> C;
    K.s = A;
    K.d = B;
    K.c = C;

    V.push_back( K );

    for( int i = 2; i < N; ++i )
    {
        K.s = (1LL * K.s * i )%N;
        K.d = (1LL * K.d * i )%N;
        K.c = (1LL * K.c * i )%N;

        V.push_back( K );
    }
    for( int i = 1; i < N; ++i )
    {
        sz[i] = 1;
    }
}

int Find( int x )
{
    int root_x = x;

    while( m[root_x] != root_x )
        root_x = m[root_x];

    while( x != root_x )
    {
        int aux = m[x];
        m[x] = root_x;
        x = aux;
    }

    return root_x;
}

void Union( int x, int y )
{
    x = Find( x );
    y = Find( y );

    if( sz[x] > sz[y] )
    {
        m[y] = x;
        sz[y] += sz[x];
        D[y] = max( D[y], D[x] );
    }
    else
    {
        m[x] = y;
        sz[y] += sz[x];
        D[x] = max( D[x], D[y] );
    }
}

void Solve()
{
    for( int i = V.size()-1; i >= 0; --i )
    {
        int lf = V[i].s;
        int rg = V[i].d;
        int col = V[i].c;

        for( int i = lf; i <= rg; ++i )
        {
            int root_i = Find( i );
            if( root_i == 0  )
            {
                S[i] = col;
                D[i] = i;
                if( i == lf )
                    m[i] = i;
                else Union( i, i-1);
            }
            else i = D[root_i];
        }
    }

    for( int i = 1; i < N; ++i )
        fout << S[i] << '\n';
}

int main()
{
    Read();
    Solve();
    return 0;
}