Cod sursa(job #2777655)

Utilizator MihneaCadar101Cadar Mihnea MihneaCadar101 Data 23 septembrie 2021 20:30:30
Problema Curcubeu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <bits/stdc++.h>
using namespace std;

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

const int nmax = 1e6;
int n, A, B, C, ans[nmax + 5], t[nmax + 5];
vector <pair <int, int> > v;
vector <int> nr;

int findd(int x) {
    while (x != t[x]) x = t[x];

    return x;
}

int main()
{
    fin >> n >> A >> B >> C;
    v.push_back({0, 0});
    nr.push_back(0);

    v.push_back({A, B});
    nr.push_back(C);
    t[1] = 1;
    for (int i = 2; i < n; ++i) {
        A = (A * i) % n;
        B = (B * i) % n;
        C = (C * i) % n;
        v.push_back({A, B});
        nr.push_back(C);
        t[i] = i;
    }

    for (int i = n - 1; i >= 1; --i) {
        int st = v[i].first, dr = v[i].second, x = nr[i];
        if (st < dr) swap(st, dr);

        while (st <= dr) {
            if (st != t[st]) {
                st = findd(++st);
                continue;
            }

            ans[st] = x;
            t[st] = dr + 1;
            if (st + 1 > dr) break;

            st = findd(++st);
        }
    }

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