Cod sursa(job #2524754)

Utilizator cyg_TheoPruteanu Theodor cyg_Theo Data 16 ianuarie 2020 11:04:20
Problema Reguli Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 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;
    for(int k=1,st=0,dr=0;k<n;++k){
        if(k>dr){
            st=dr=k;
            while(dr<n && s[dr]==s[dr-st])
                dr++;
            z[k]=dr-st;
            dr--;
        }else{
            if(k+z[k-st]<=dr)
                z[k]=z[k-st];
            else{
                st=k;
                while(dr<n && s[dr]==s[dr-st])
                    dr++;
                z[k]=dr-st;
                dr--;
            }
        }
    }
    int ans=n;
    for(int i=1;i<n;++i){
        if(z[i]>=i){
            int len=(z[i]/i+1)*i;
            //printf("%d %d %d %d\n",i,z[i],len,z[len+1]);
            if(len==n-1)
                ans=min(ans,i);
        }
    }
    printf("%d\n",ans);
    for(int i=0;i<ans;++i)
        printf("%lld\n",s[i]);
    return 0;
}