Cod sursa(job #1876428)

Utilizator mirunazMiruna Zavelca mirunaz Data 12 februarie 2017 13:04:41
Problema Curcubeu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <cstdio>
#include <algorithm>
using namespace std;

#define max 1000003

int n, a[max], b[max], c[max], v[max], boss[max];

int Find (int x)
{
    if (boss[x] == 0){
        return x;
    }
    boss[x] = Find (boss[x]);
    return boss[x];
}

void Union (int left, int right, int color)
{
    while (left <= right){
        if (v[left] != 0){
            left = Find (left);
        }
        if (left <= right){
            v[left] = color;
            boss[left] = right + 1;
            left ++;
        }
    }
}

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