Cod sursa(job #2457969)

Utilizator mircearoataMircea Roata Palade mircearoata Data 19 septembrie 2019 10:50:07
Problema Reguli Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <iostream>
#include <fstream>

using namespace std;

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

long long n, x;
long long v[500001];
int ans;
int phi[500001];

int main()
{
	in >> n >> v[0];
	n--;
	for (int i = 1; i <= n; i++)
	{
		in >> x;
		v[i] = x - v[0];
		v[0] = x;
	}
	phi[1] = 0;
	for (int i = 2; i <= n; i++)
	{
		int x = i - 1;
		while (v[phi[x] + 1] != v[i] && phi[x])
			x = phi[x];
		if (v[phi[x] + 1] == v[i])
			phi[i] = phi[x] + 1;
		else
			phi[i] = 0;
		if (phi[i] == 1)
			ans = i - 1;
	}
	if (ans == 0)
		ans = n;
	out << ans << '\n';
	for (int i = 1; i <= ans; i++)
		out << v[i] << '\n';
}