Cod sursa(job #2916278)

Utilizator raul41917raul rotar raul41917 Data 28 iulie 2022 19:02:30
Problema Reguli Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <iostream>
#include <fstream>

using namespace std;
ifstream fi("reguli.in");
ofstream fo("reguli.out");
int N;
int d_Array[500002];
int LPS[500002];
void Solve(int N)
{
    int len=0;
    LPS[0]=0;
    int i=1;
    while(i<=N)
    {
        if(d_Array[i]==d_Array[len])
        {
            len++;
            LPS[i]=len;
            i++;
        }else
        {
            if(len!=0)
                len=LPS[len-1];
            else
            {
                LPS[i]=0;
                i++;
            }
        }
    }
}
int main()
{
    fi>>N;
    int x;
    fi>>x;
    for(int i=1;i<N;i++)
    {
        int y;
        fi>>y;
        int D=y-x;
        d_Array[i-1]=D;
        x=y;
    }
    N--;
    Solve(N);
    N=N-LPS[N-1];
    fo<<N<<"\n";
    for(int i=0;i<N;i++)
        fo<<d_Array[i]<<"\n";
    return 0;
}