Cod sursa(job #2629361)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 20 iunie 2020 12:43:22
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>

using namespace std;

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

const int NMAX = 5e5 + 5;

int N;

long long A[NMAX], B[NMAX];

int phi[NMAX];

static inline void Read ()
{
    f.tie(nullptr);

    f >> N;

    for(int i = 1; i <= N; ++i)
        f >> A[i];

    for(int i = 1; i < N; ++i)
        B[i] = A[i + 1] - A[i];

    return;
}

static inline void KMP ()
{
    phi[1] = 0;

    int ans = 0;

    for(int i = 2; i < N; ++i)
    {
        while(ans && B[i] != B[ans + 1])
            ans = phi[ans];

        if(B[i] == B[ans + 1])
            ++ans;

        phi[i] = ans;
    }

    return;
}

static inline void Solve ()
{
    int ans = (N - 1) - phi[(N - 1)];

    g << ans << '\n';

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

    return;
}

int main()
{
    Read();

    KMP();

    Solve();

    return 0;
}