Cod sursa(job #2733215)

Utilizator CatalinPangaleanuCatalin Pangaleanu CatalinPangaleanu Data 30 martie 2021 09:40:24
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <fstream>

using namespace std;

ifstream fin("reguli.in");
ofstream fout("reguli.out");

int lps[500001];
long long v[500001];

int main()
{   ios::sync_with_stdio(false);
    fin.tie(nullptr), fout.tie(nullptr);
    int n, i, j;
    long long x, y;
    fin>>n>>x;
    for (i=1;i<n;++i)
    {   fin>>y;
        v[i]=y-x;
        x=y;
    }
    fin.close();
    j=0;
    for (i=2;i<n;++i)
    {   while (j && v[i]!=v[j+1])
            j=lps[j-1];
        if (v[i]==v[j+1])
            ++j;
        lps[i]=j;
    }
    fout<<n-1-lps[n-1];
    for (i=1;i<=n-1-lps[n-1];++i)
        fout<<'\n'<<v[i];
    fout.close();

    return 0;
}