Cod sursa(job #2458264)

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

using namespace std;

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

void KermitManancaPrune()
{
	memset(phi, 0, sizeof(phi));
	phi[1] = 0;
	for (int i = 2; i <= n; i++)
	{
		int 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;
	int val;
	cin >> val;
	n--;
	for(int i = 1 ; i <= n ; i++)
    {
        cin >> x;
        v[i] = x - val;
        val = x;
    }
    KermitManancaPrune();
    cout << n-phi[n] << "\n";
    for(int i = 1 ; i <= n-phi[n] ; i++)
        cout << v[i] << "\n";
	return 0;
}