Cod sursa(job #1977636)

Utilizator brczBereczki Norbert Cristian brcz Data 5 mai 2017 18:08:18
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
// #include<bits/stdc++.h>
#include<fstream>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define sz size
#define pb push_back
#define mp make_pair
#define bg begin
#define nd end
using namespace std;

#define int long long

const int maxn = 500003;
const int maxk = 1003;

int pref[maxn];
int arr[maxn];
int n;
void kmp(){

	int q = 0;
	pref[1] =0;
	for(int i=2;i<n;i++){

		while(q && arr[q+1]!=arr[i]){
			q = pref[q];
		}
		if(arr[q+1] == arr[i]) q++;

		pref[i] = q;
	}
}

int32_t main(){

	// #ifndef ONLINE_JUDGE
	// freopen("reguli.in","r",stdin);
	// #endif
	ifstream fin("reguli.in");
	ofstream fout("reguli.out");

	ios_base::sync_with_stdio(false);

	fin >> n;
	int x,bef;
	for(int i=0;i<n;i++){
		fin >> x;
		if(i > 0){
			arr[i] = x - bef;
		}
		bef = x;
	}
	kmp();
	fout << n-pref[n-1] - 1 << '\n';
	for(int i=1;i<n-pref[n-1];i++){
		fout << arr[i] << '\n';
	}

	return 0;
}