Cod sursa(job #2637303)

Utilizator andreic06Andrei Calota andreic06 Data 22 iulie 2020 13:17:20
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <iostream>
#include <fstream>

using namespace std;
const int N = 5e5;
long long dif[N+1], lps[N];

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

int n;
long long x, y;
void process_prefix () {
    int len = 0;
    lps[0] = 0;

    for ( int i = 1; i < n; i ++ ) {
       while ( len > 0 && dif[len] != dif[i] )
          len = lps[len-1];
      if ( dif[len] == dif[i] )
        len ++;
      lps[i] = len;
    }
}
int main()
{
   fin >> n >> x;
   for ( int i = 1; i < n; i ++ ) {
     fin >> y, dif[i-1] = y - x;
     x = y;
   }
   process_prefix ();

   int res = n - 1 - lps[n-2];
   fout << res << '\n';
   for ( int j = 0; j < res; j ++ )
      fout << dif[j] << '\n';
    return 0;
}