Cod sursa(job #2245282)

Utilizator GeoeyMexicanuBadita George GeoeyMexicanu Data 24 septembrie 2018 23:46:55
Problema Reguli Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream f("reguli.in");
ofstream g("reguli.out");
int v[500010],d[500010],i,j,n,ans,lps[500010],q,nr;

void prefix(int d[500010])
{
    q=0;
    lps[q]=0;
    for(i=2;i<n;i++)
    {
        while(q && d[q+1]!=d[i])
            q=lps[q];
        if(d[q+1]==d[i])
            q++;
        lps[i]=q;
        if(i%(i-lps[i])==0)
        {
            ans=i;
        }
    }
    g<<ans-lps[ans]<<'\n';
    for(i=ans-lps[ans]+1;i<=ans;i++)
        g<<d[i]<<'\n';
}
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i];
    for(i=2;i<=n;i++)
        d[i-1]=v[i]-v[i-1];
    prefix(d);
}