Cod sursa(job #1417785)

Utilizator tatianazTatiana Zapirtan tatianaz Data 10 aprilie 2015 22:59:45
Problema Curcubeu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <fstream>
#include <algorithm>
using namespace std;

ifstream is("curcubeu.in");
ofstream os("curcubeu.out");

int n;
int col[1000001], nex[1000001];
int aa, bb, cc;

struct Case{
    int a, b, c;
};

Case x[1000001];

int FindGr(int i)
{
    if (nex[i] == i)
        return nex[i];
    nex[i] = FindGr(nex[i]);
    return nex[i];
}

void Combine(int i, int j)
{
    nex[i] = FindGr(j);
}

int main()
{
    is >> n;
    is >> aa >> bb >> cc;
    x[1].a = min(aa, bb);
    x[1].b = max(aa, bb);
    x[1].c = cc;
    nex[1] = 1;
    for (int i = 2; i < n; ++i)
    {
        nex[i] = i;

        aa = (1LL * x[i-1].a * i) % n;
        bb = (1LL * x[i-1].b * i) % n;
        cc = (1LL * x[i-1].c * i) % n;

        x[i].a = min(aa, bb);
        x[i].b = max(aa, bb);
        x[i].c = cc;
    }

    for (int i = n - 1; i >= 1; --i)
        for (int j = x[i].a; j <= x[i].b; ++j)
            if (nex[j] != j)
            {
                j = nex[j];
                continue;
            }
            else
            {
                if (!col[j])
                {
                    col[j] = x[i].c;
                    Combine(j, x[i].b);
                }
            }

    for (int i = 1; i < n; ++i)
       os << col[i] << '\n';

    is.close();
    os.close();
    return 0;
}