Cod sursa(job #1893241)

Utilizator ciprianprohozescuProhozescu Ciprian ciprianprohozescu Data 25 februarie 2017 16:04:01
Problema Curcubeu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
#define NMAX 1000010

using namespace std;

ifstream fin("curcubeu.in");
FILE *fout;

int a[NMAX], b[NMAX], c[NMAX], tata[NMAX], v[NMAX], n;

int Find(int x);
void Union(int st, int dr, int c);

int main()
{
    int i;
    fout = fopen("curcubeu.out", "w");
    fin >> n >> a[1] >> b[1] >> c[1];
    for (i = 2; i < n; i++)
    {
        a[i] = ((long long) a[i - 1] * i) % n;
        b[i] = ((long long) b[i - 1] * i) % n;
        c[i] = ((long long) c[i - 1] * i) % n;
    }
    for (i = n - 1; i >= 1; i--)
        Union(a[i], b[i], c[i]);
    for (i = 1; i < n; i++)
        fprintf(fout, "%d\n", v[i]);
    fclose(fout);
    return 0;
}

int Find(int x)
{
    int rad = x;
    while (tata[rad])
        rad = tata[rad];
    /*if (x != rad)
    {
        while (tata[x] != rad)
        {
            aux = tata[x];
            tata[x] = rad;
            x = aux;
        }
    }*/
    return rad;
}
void Union(int st, int dr, int c)
{
    if (st > dr)
        swap(st, dr);
    while (st <= dr)
    {
        if (v[st])
            st = Find(st);
        if (st <= dr)
        {
            v[st] = c;
            tata[st] = dr + 1;
            st++;
        }
    }
}