Cod sursa(job #2561236)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 28 februarie 2020 17:56:42
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 500005;

int N;
long long a[NMAX];
long long v[NMAX];
int lps[NMAX];

void Read()
{
    fin >> N;
    for( int i = 1; i <= N; ++i )
      fin >> a[i];
}

void Lps()
{
    int lg = 0;

    for( int i = 1; i < N; ++i )
      if( v[i] == v[lg] ) lps[i] = ++lg;
      else
        if( lg > 0 ) {
           lg = lps[lg - 1];
           --i;
        }
}

void Do()
{
    for( int i = 1; i < N; ++i )
      v[i - 1] = a[i + 1] - a[i];

    --N;

    Lps();

    /*for( int i = 0; i < N; ++i )
      fout << v[i] << ' ';
    fout << '\n';
    for( int i = 0; i < N; ++i )
      fout << lps[i] << ' ';*/

    int p = N;

    for( int i = N - 1; i >= 0; --i )
      if( ( i == N - 1 || lps[i] == lps[i + 1] - 1 ) && lps[i] ) p = i;
      else break;

    fout << p << '\n';
    for( int i = 0; i < p; ++i )
      fout << v[i] << '\n';
}

int main()
{
    Read();
    Do();

    return 0;
}