Cod sursa(job #2733203)

Utilizator CatalinPangaleanuCatalin Pangaleanu CatalinPangaleanu Data 30 martie 2021 09:13:25
Problema Reguli Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.93 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=1;
    for (i=2;i<n;)
        if (v[i]==v[j])
        {   lps[i]=j;
            ++j;
            ++i;
        }
        else
            if (j>1)
                j=lps[j-1];
            else
                ++i;
    for (i=n-1;i>=2;--i)
        if (lps[i] && !(i%(i-lps[i])))
        {   fout<<i-lps[i];
            for (j=i-lps[i]+1;j<=i;++j)
                fout<<'\n'<<v[j];
            fout.close();
            return 0;
        }
    fout<<n-1;
    for (i=1;i<n;++i)
        fout<<'\n'<<v[i];
    fout.close();

    return 0;
}