Cod sursa(job #1171686)

Utilizator andreiagAndrei Galusca andreiag Data 16 aprilie 2014 07:41:54
Problema Curcubeu Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <fstream>
#include <iostream>
#include <string.h>

using namespace std;
const int Nmax = 1000033;
typedef long long ll;

int E[Nmax][3];
int col[Nmax];
int Nxt[Nmax];

int last(int x)
{
    if (x != Nxt[x])
        Nxt[x] = last(Nxt[x]);
    return Nxt[x];
}


int main()
{
    ifstream f ("curcubeu.in");
    ofstream g ("curcubeu.out");

    ll N, A, B, C;
    f >> N >> A >> B >> C;

    for (int i = 1; i < N; i++)
    {
        if (A < B)
            { E[i][0] = A; E[i][1] = B; }
        else
            { E[i][0] = B; E[i][1] = A; }
        E[i][2] = C;

        A = (A*(i+1)) % N;
        B = (B*(i+1)) % N;
        C = (C*(i+1)) % N;
    }

    memset(col, 0, sizeof(col));
    memset(Nxt, -1, sizeof(Nxt));

    for (int i = N-1; i >= 1; i--)
    {
        int x = E[i][0], y = E[i][1], z = E[i][2];
        while(x <= y)
        {
            if (!col[x])
            {
                col[x] = z;
                Nxt[x] = x;
                if (col[x-1] == z)
                    Nxt[x-1] = x;
            } else
            {
                if (col[x-1] == col[x])
                    Nxt[x-1] = x;
                x = last(x);
            }
            x++;
        }
    }
    for (int i = 1; i < N; i++)
        g << col[i] << '\n';
    

    return 0;
}