Cod sursa(job #1458409)

Utilizator valentin50517Vozian Valentin valentin50517 Data 7 iulie 2015 14:37:34
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
#include <fstream>
#define LL long long
using namespace std;
ifstream fin("reguli.in");
ofstream fout("reguli.out");

LL A[500003];
int N, pi[500006],maxi,pos,rs;

void gen_prefix(){
	int q = 0,i;
	pi[1] = 0;
	for(i = 2;i<=N;i++){
		while(q && A[q+1] != A[i])
			q = pi[q];
		if(A[q+1] == A[i])
			q++;
		pi[i] = q;
		if(q == 1) rs = i-1;
		if(q == 0) rs = i;
	}
	if(!rs) rs = N; 
}

int main(){
	fin >> N;
	N--;
	int i,x,x1;
	fin >> x;
	for(i = 1;i<=N;i++){
		fin >> x1;
		A[i] = x1-x;
		x = x1;
	}
	gen_prefix();
	fout << rs << '\n';
	for(i = 1;i<=rs;i++) fout << A[i] << '\n';
	
	return 0;
}