Cod sursa(job #2725281)

Utilizator Albert_GAlbert G Albert_G Data 18 martie 2021 18:31:07
Problema Reguli Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <fstream>

using namespace std;

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

const int N = 5e5;
long long dif[N+2];
int lps[N+2];

int main()
{
    int n;
    in>>n;
    int x;
    in>>x;
    --n;
    for(int i=1;i<=n;++i){
        int y;
        in>>y;
        dif[i]=y-x;
        x=y;
    }
    lps[1]=0;
    int len=0,lmax=0;
    for(int i=2;i<=n;++i){
        while(len && dif[i]!=dif[len+1]){
            len=lps[len-1];
        }
        if(dif[len+1]==dif[i]){
            ++len;
        }
        lps[i] = len;
    }
    lmax = n-lps[n];
    out<<lmax<<'\n';
    for(int i=1;i<=lmax;++i){
        out<<dif[i]<<'\n';
    }
    return 0;
}