Cod sursa(job #2458265)

Utilizator ardutgamerAndrei Bancila ardutgamer Data 20 septembrie 2019 01:04:00
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

const int NMAX = 500005;
long long phi[NMAX];
long long v[NMAX];
long long n;
long long x;

void KermitManancaPrune()
{
	memset(phi, 0, sizeof(phi));
	phi[1] = 0;
	for (long long i = 2; i <= n; i++)
	{
		long long x = i - 1;
		while (v[phi[x] + 1] != v[i] && x)
			x = phi[x];
		if (v[phi[x] + 1] == v[i])
			phi[i] = phi[x] + 1;
		else
			phi[i] = 0;
	}
}

int main()
{
	ifstream cin("reguli.in");
	ofstream cout("reguli.out");
	cin >> n;
	long long val;
	cin >> val;
	n--;
	for(long long i = 1 ; i <= n ; i++)
    {
        cin >> x;
        v[i] = x - val;
        val = x;
    }
    KermitManancaPrune();
    cout << n-phi[n] << "\n";
    for(long long i = 1 ; i <= n-phi[n] ; i++)
        cout << v[i] << "\n";
	return 0;
}