Cod sursa(job #3240682)

Utilizator stefan_dore_Stefan Dore stefan_dore_ Data 19 august 2024 19:48:14
Problema Curcubeu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream f ("curcubeu.in");
ofstream g ("curcubeu.out");

const int NMAX = 1000000;
int N, T[NMAX+1], C[NMAX+1], a[NMAX+1], b[NMAX+1], c[NMAX+1];

int Find(int i) {
    if (T[i] == 0) return i;
    return T[i] = Find(T[i]);
}

void Union(int cx, int cy) {
    if (cx != cy)
        T[cx] = cy;
}

int main()
{
    f >> N >> a[1] >> b[1] >> c[1];
    if (a[1] > b[1])
        swap(a[1], b[1]);
    for (int i=2; i<=N-1; 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--) {
        int cx = Find(a[i]), cy = Find(b[i]+1);
        while(cx <= b[i]) {
            C[cx] = c[i];
            Union(cx, cy);
            cx = Find(cx+1);
        }
    }
    for (int i=1; i<=N-1; i++)
        g << C[i] << '\n';
    f.close();
    g.close();
    return 0;
}