Cod sursa(job #2457967)

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

using namespace std;

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

#define int long long

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

int32_t 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;
	}
	out << ans << '\n';
	for (int i = 1; i <= ans; i++)
		out << v[i] << '\n';
}