Cod sursa(job #1107409)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 13 februarie 2014 21:17:44
Problema Curcubeu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <cstdio>

using namespace std;

const int NMax = 1000010;

int n;
int a[NMax], b[NMax], c[NMax];
bool colored[NMax];
int comp[NMax];
int ans[NMax];

inline void swap(int &x, int &y)
{
    int aux = x; x = y; y = aux;
}

inline int find(int x)
{
    int root, y;
    root = x;
    for (; root != comp[root]; root = comp[root]);
    for (; comp[x] != root; y = comp[x], comp[x] = root, x = y);
    return root;
}

int main()
{
    freopen("curcubeu.in", "r", stdin);
    scanf("%d %d %d %d", &n, &a[1], &b[1], &c[1]);
    if (a[1] > b[1])
        swap(a[1], b[1]);
    for (int i = 1; i <= n; ++i)
        comp[i] = i;
    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]);
    }
    for (int i = n - 1; i >= 1; --i)
    {
        for (int j = a[i]; j <= b[i];)
        {
            if (!colored[j])
            {
                colored[j] = true;
                ans[j] = c[i];
                comp[j] = b[i] + 1;
                ++j;
            }
            else
                j = find(j);
        }
    }
    freopen ("curcubeu.out", "w", stdout);
    for (int i = 1; i < n; ++i)
        printf("%d\n", ans[i]);
    return 0;
}