Cod sursa(job #2616910)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 20 mai 2020 11:58:07
Problema Curcubeu Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <bits/stdc++.h>

using namespace std;

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

const int DIM = 1e6 + 1;

int to[DIM];
int l[DIM];
int r[DIM];
int c[DIM];
int ans[DIM];

int get(int nod)
{
    if(nod == to[nod])
        return nod;

    return (to[nod] = get(to[nod]));
}

void unite(int x, int y)
{
    if(x == y)
        return ;

    to[x] = y;
}

main()
{
    int n;
    fin >> n;

    fin >> l[1] >> r[1] >> c[1];

    if(l[1] > r[1])
        swap(l[1], r[1]);

    to[1] = 1;

    for(int i = 2; i < n; ++i)
    {
        l[i] = (l[i - 1] * 1LL * i) % n;
        r[i] = (r[i - 1] * 1LL * i) % n;
        c[i] = (c[i - 1] * 1LL * i) % n;

        if(l[i] > r[i])
            swap(l[i], r[i]);

        to[i] = i;
    }

    to[n] = n;

    for(int i = n - 1; i >= 1; --i)
    {
        int st = get(l[i]);

        while(st <= r[i])
        {
            unite(st, r[i]);

            if(ans[st] == 0)
            {
                ans[st] = c[i];
            }

            st = get(st + 1);
        }
    }

    for(int i = 1; i < n; ++i)
        fout << ans[i] << '\n';
}