Cod sursa(job #2725275)

Utilizator Albert_GAlbert G Albert_G Data 18 martie 2021 18:19:28
Problema Reguli Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <fstream>

using namespace std;

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

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

int main()
{
    int n;
    in>>n;
    int x;
    in>>x;
    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]){
            lps[i] = len;
            ++len;
        }
        else{
            lps[i] = 0;
        }
        if(len && i%(i-len)==0){
            lmax = max(lmax,len);
        }
    }
    out<<lmax<<'\n';
    for(int i=1;i<=lmax;++i){
        out<<dif[i]<<'\n';
    }
    return 0;
}