Cod sursa(job #996196)

Utilizator sleepaholicNeculaescu Theodor sleepaholic Data 11 septembrie 2013 12:39:44
Problema Curcubeu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <iostream>
#include <fstream>

using namespace std;

const int Nmax = 1000005;

int A[Nmax], B[Nmax], C[Nmax];
int Next[Nmax], answer[Nmax];

int N;

void read()
{
    ifstream f("curcubeu.in");

    f >> N >> A[1] >> B[1] >> C[1];

    f.close();
}

void gen()
{
    for ( int i = 2; i < N; ++i )
    {
        A[i] = ( 1LL * A[i - 1] * i ) % N;
        B[i] = ( 1LL * B[i - 1] * i ) % N;
        C[i] = ( 1LL * C[i - 1] * i ) % N;
    }

    for ( int i = 1; i <= N; ++i )
            Next[i] = i;
}

void solve()
{
    for ( int i = N - 1; i >= 1; i-- )
    {
        int st = A[i];
        int dr = B[i];
        int color = C[i];
        int poz;

        if ( st > dr )
        {
            st ^= dr;
            dr ^= st;
            st ^= dr;
        }

        for ( poz = st; poz <= dr; )
        {
            while( Next[poz] != poz && poz <= dr )
                    poz = Next[poz];

            if ( poz > dr ) continue;

            answer[poz] = color;
            Next[poz] = dr + 1;
            poz++;
        }
    }
}

void print()
{
    ofstream g("curcubeu.out");

    for ( int i = 1; i < N; ++i )
            g << answer[i] << "\n";

    g.close();
}

int main()
{
    read();
    gen();
    solve();
    print();

    return 0;
}