Cod sursa(job #2561212)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 28 februarie 2020 17:45:09
Problema Reguli Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 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 - 1;

    for( int i = N - 2; i >= 0; --i )
      if( 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;
}