Cod sursa(job #2567737)

Utilizator Teo_1101Mititelu Teodor Teo_1101 Data 3 martie 2020 18:38:45
Problema Curcubeu Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.66 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;

        if( K.s > K.d ) swap( K.s, K.d );

        V.push_back( K );
    }

}

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 )
        {
            if( D[i] != 0 )
                i = D[i];
            else
            {
                S[i] = col;
            }
            D[i] = rg;
        }
    }

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

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