Cod sursa(job #2524756)

Utilizator cyg_TheoPruteanu Theodor cyg_Theo Data 16 ianuarie 2020 11:12:01
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

const int NMAX = 500005;

long long s[NMAX];
int z[NMAX];

int main(){
    freopen("reguli.in","r",stdin);
    freopen("reguli.out","w",stdout);
    int n;
    scanf("%d",&n);
    long long x,y;
    scanf("%lld",&y);
    n--;
    for(int i=0;i<n;++i){
        scanf("%lld",&x);
        s[i]=x-y;
        y=x;
    }
    ///make z function
    z[0]=0;
    int q=0;
    for(int k=1;k<n;++k){
        while(q && s[q]!=s[k])
            q=z[q-1];
        if(s[q]==s[k])
            ++q;
        z[k]=q;
    }

    printf("%d\n",n-z[n-1]);
    for(int i=0;i<n-z[n-1];++i)
        printf("%lld\n",s[i]);
    return 0;
}