Cod sursa(job #3238802)

Utilizator GabrielPopescu21Silitra Gabriel - Ilie GabrielPopescu21 Data 30 iulie 2024 16:40:40
Problema Curcubeu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <bits/stdc++.h>
using namespace std;

const int MAX = 1e6+5;
int parent[MAX], ans[MAX];

struct Point {
    int a, b, c;
} a[MAX];

int FindRoot(int node)
{
    if (parent[node] == node)
        return node;

    return parent[node] = FindRoot(parent[node]);
}

int main()
{
    ifstream cin("curcubeu.in");
    ofstream cout("curcubeu.out");
    int n;
    cin >> n >> a[1].a >> a[1].b >> a[1].c;

    if (a[1].a > a[1].b)
        swap(a[1].a, a[1].b);

    parent[1] = 1;

    for (int i = 2; i < n; ++i)
    {
        a[i].a = (a[i-1].a * i) % n;
        a[i].b = (a[i-1].b * i) % n;
        a[i].c = (a[i-1].c * i) % n;

        if (a[i].a > a[i].b)
            swap(a[i].a, a[i].b);

        parent[i] = i;
    }

    for (int i = n-1; i >= 1; --i)
    {
        int p = FindRoot(a[i].a);
        while (p <= a[i].b)
        {
            ans[p] = a[i].c;
            parent[p] = a[i].b+1;
            p = FindRoot(p+1);
        }
    }

    for (int i = 1; i <= n-1; ++i)
        cout << ans[i] << "\n";

    return 0;
}