Cod sursa(job #2245285)

Utilizator GeoeyMexicanuBadita George GeoeyMexicanu Data 24 septembrie 2018 23:53:27
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 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;
    }
    ans=n-lps[n-1]-1;
    g<<ans<<'\n';
    for(i=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);
    return 0;
}