Cod sursa(job #2775197)

Utilizator euyoTukanul euyo Data 14 septembrie 2021 21:17:16
Problema Reguli Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <fstream>
#define ll long long

using namespace std;

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

const int MAXN = (int)5e5 + 1;

ll v[MAXN];
int pi[MAXN];

inline void getpi( int m ) {
  int q = 0;
  for ( int i = 2; i <= m; ++i ) {
    while ( q > 0 && v[q] != v[i - 1] ) {
      q = pi[q];
	}
	if ( v[q] == v[i - 1] ) {
	  ++q;
	}
    pi[i] = q;
  }
}

int main() {
  int n;
  ll x, y;

  fin >> n >> x;
  for ( int i = 1; i < n; ++i ) {
	fin >> y;
	v[i - 1] = y - x;
    //fout << v[i - 1] << " "; 
	x = y;
  }
  //fout << "\n";
  --n;
  getpi( n );
  int k = n;
  for ( ; k >= 1; --k ) {
    if ( k % (k - pi[k]) == 0 && pi[k] != 0 ) {
	  break;
	}	
  }
  if ( pi[n] < n - k ) {
	fout << n << "\n";
	for ( int i = 0; i < n; ++i ) {
	  fout << v[i] << "\n";
	}
	return 0;
  }
  while ( k >= 1 && pi[k] != 0 ) {
	k = pi[k];
  }
  if ( k == 0 ) {
	fout << n << "\n";
	for ( int i = 0; i < n; ++i ) {
	  fout << v[i] << "\n";
	}
  } else {
    fout << k << "\n"; 
    for ( int i = 0; i < k; ++i ) {
	  fout << v[i] << "\n";
    }
  }
  fin.close();
  fout.close();
  return 0;
}