Cod sursa(job #2607421)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 29 aprilie 2020 18:46:09
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <fstream>

using namespace std;

ifstream cin("reguli.in");
ofstream cout("reguli.out");

const int NMAX = 5e5;

int N;
long long a[NMAX + 2], dif[NMAX + 2], pi[NMAX + 2];

int main()
{
	cin >> N;
	cin >> a[0];

	for(int i = 1; i < N; i++)
		{
			cin >> a[i];
			dif[i] = a[i] - a[i - 1];
		}

		/*
	for(int i = 1; i < N; i++)
		cout << dif[i] << ' ';
		*/
	
	int j = 0;
	for(int i = 2; i < N; i++)
	{
		while(j && dif[i] != dif[j + 1])
			j = pi[j];

		if(dif[i] == dif[j + 1])
			j++;

		pi[i] = j;
	}

	int len = N - 1 - pi[N - 1];

	cout << len << '\n';
	for(int i = 1; i <= len; i++)
		cout << dif[i] << '\n';

	return 0;
}