Cod sursa(job #1171689)

Utilizator andreiagAndrei Galusca andreiag Data 16 aprilie 2014 09:37:02
Problema Curcubeu Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 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++)
    {
        nxt[i] = 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;
    }
    for (int i = N;  i < N+10; i++)
        nxt[i] = i;
    memset(col, 0, sizeof(col));

    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] = y+1;
                x++;
            }
            else
            {
                x = last(x);
            }
        }
    }
    for (int i = 1; i < N; i++)
        g << col[i] << '\n';
    

    return 0;
}