Cod sursa(job #2562218)

Utilizator Teo_1101Mititelu Teodor Teo_1101 Data 29 februarie 2020 12:50:52
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 500005;

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

long long lps[NMAX];
long long N, x, y, V[NMAX];

void LPS()
{
    lps[0] = 0;

    for( int i = 1; i < N; ++i )
        if( V[i] == V[lps[i-1]])
            lps[i] = lps[i-1]+1;
        else
        {
            int lg = lps[i-1];

            while( lg  && V[i] != V[lg] )
                lg = lps[lg-1];

            if( V[i] == V[lg] ) lps[i] = lg+1;
        }
    //for( int i = 0; i < N; ++i )cout << lps[i] << ' ';
}
void Solve()
{
    fin >> N;
    fin >> x;
    for( int i = 1; i < N; ++i )
    {
        fin >> y;
        V[i-1] = y-x;
        x = y;
    }N--;

    LPS();

    int P = N - lps[N-1];

    fout << P << '\n';

    for( int i = 0; i < P; ++i )
        fout << V[i] << '\n';
}
int main()
{
    Solve();
    return 0;
}