Cod sursa(job #2923688)

Utilizator lolismekAlex Jerpelea lolismek Data 17 septembrie 2022 20:39:45
Problema Reguli Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int N = 5e5;
int v[N + 1], kmp[N + 1], f[N + 1];

void Kmp(int n){
	for(int i = 2; i <= n; i++){
		int l = kmp[i - 1];
		while(l >= 1 && v[l + 1] != v[i])
			l = kmp[l];
		if(v[l + 1] == v[i])
			kmp[i] = l + 1;
	}
}

int main(){

	int n, x0;
	fin >> n >> x0, n--;

	int sub = 0;
	for(int i = 1; i <= n; i++){
		fin >> v[i], v[i] -= x0;
		v[i] -= sub, sub += v[i];
	}

	Kmp(n);

	int ind = n;
	while(kmp[ind] != 0)
		ind -= kmp[ind];

	fout << ind << '\n';
	for(int i = 1; i <= ind; i++)
		fout << v[i] << '\n';
	
	return 0;
}