Cod sursa(job #1979320)

Utilizator FrequeAlex Iordachescu Freque Data 10 mai 2017 10:54:21
Problema Curcubeu Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

ifstream fin("curcubeu.in");
ofstream fout("curcubeu.out");

const int NMAX = 1000000 + 5;

int n, n2;
int a[NMAX], b[NMAX], c[NMAX], vect[NMAX], lung[NMAX], t[NMAX];
bool painted[NMAX];

void read()
{
    fin >> n >> a[1] >> b[1] >> c[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;
        if (a[i] > b[i])
            swap(a[i], b[i]);
    }
    --n;
    for (int i = 1; i <= n; ++i)
        lung[i] = 1;
}

int findy(int a)
{
    int r = a;
    while (t[r])
        r = t[r];
    int x, y;
    x = a;
    while (x != r)
    {
        y = t[x];
        t[x] = r;
        x = y;
    }
    return r;
}

void unite(int a, int b)
{
    a = findy(a);
    b = findy(b);
    if (a == b)
        return ;
    t[b] = a;
    lung[a] += lung[b];
}

void rainbow(int x, int y, int cul)
{
    for (int i = x; i <= y; i += lung[i])
    {
        if (!painted[i])
        {
            vect[i] = cul;
            painted[i] = 1;
            if (i >= 2 && painted[i - 1])
                unite(i - 1, i);
            if (i < n && painted[i + 1])
                unite(i, i + 1);
        }
        i = findy(i);
    }
}

int main()
{
    read();
    for (int i = n; i >=1; --i)
        rainbow(a[i], b[i], c[i]);
    for (int i = 1; i <= n; ++i)
        fout << vect[i] << '\n';
    return 0;
}