Cod sursa(job #2299813)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 10 decembrie 2018 10:21:47
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <bits/stdc++.h>

using namespace std;

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

constexpr int NMAX=1e6+5;

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

int N, i;

int PHI[NMAX];

void Precalculation ()
{
    int ans=0;

    PHI[1]=0;

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

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

        PHI[i]=ans;
    }
}

void Solve ()
{
    int ans=(N-1)-PHI[N-1];

    g<<ans<<'\n';

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

int main()
{
    f.tie(NULL);

    f>>N;

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

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

    Precalculation();

    Solve();

    return 0;
}