Cod sursa(job #1518290)

Utilizator zertixMaradin Octavian zertix Data 5 noiembrie 2015 20:02:40
Problema Reguli Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <iostream>
#include <cstdio>
#define lim 500100
using namespace std;

long long dif[lim],pref[lim],x,y;
int n,maxim;

int prefix()
{
    int i=1,j=2;
    pref[1]=1;
    while (j<n)
    {
        pref[j]=1;
        if (dif[i]!=dif[j])
            if (i!=1)
                i=pref[i-1];
            else
                ++j;
        else
        {
            pref[j]=i+1;

            if (pref[j]>maxim)
                maxim=pref[j];
            ++i;
            ++j;
        }
    }
    for(int m=n; m>0; --m)
        if ( pref[m] && m+1-pref[m] && ((m+1)%(m+1-pref[m]))==0)
            return maxim=m+1-pref[m];
    return 0;
}

int main()
{
    freopen("reguli.in","r",stdin);
    freopen("reguli.out","w",stdout);
    scanf("%d",&n);
    for (int i=0;i<n;++i)
        {
            scanf("%lld",&y);
            dif[i]=y-x;
            x=y;
        }
    int lun=prefix();
    printf("%d\n",lun);
    for (int i=1;i<=lun;++i)
        printf("%lld\n",dif[i]);

    return 0;
}