Cod sursa(job #991435)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 30 august 2013 15:22:16
Problema Curcubeu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <iostream>
#include <fstream>

using namespace std;

const int Nmax = 1000005;

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

int N;

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

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

    f.close();
}

void gen()
{
    Next[1] = 1;
     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;
        Next[i]=i;
    }
}

void solve()
{
    int i,poz,start,finish,color;

    for(i=N-1;i>0;i--)
    {
        start=A[i];
        finish=B[i];
        if(start>finish)
            swap(start,finish);
        color=C[i];
        poz=start;
        while(poz<=finish)
        {
            while(Next[poz]!=poz && poz<=finish)
                poz=Next[poz];
            if(poz>finish)
                continue;
            answer[poz]=color;
            Next[poz]=finish+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;
}