Cod sursa(job #2759700)

Utilizator valentinchipuc123Valentin Chipuc valentinchipuc123 Data 19 iunie 2021 22:49:48
Problema Reguli Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <bits/stdc++.h>

using namespace std;

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

int v[500005],dif[500005],pi[500005];

int main()
{
    int n,ct=0;

    f>>n;
    n--;

    for(int i=0; i<=n; i++)
    {
        f>>v[i];

        if(i)
        {
            dif[++ct]=v[i]-v[i-1];
        }
    }

    int j=0,ans;

    for(int i=2; i<=ct; i++)
    {
        while( j && dif[i]!=dif[j+1] )
            j=pi[j];

        if( dif[i]==dif[j+1] )
            j++;

        pi[i]=j;
    }

    ans=ct-pi[ct];

    g<<ans<<'\n';

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

    return 0;
}