Cod sursa(job #2464714)

Utilizator HumikoPostu Alexandru Humiko Data 28 septembrie 2019 20:27:20
Problema Reguli Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <cstring>

using namespace std;

//#include <iostream>
#include <fstream>

//ifstream cin ("input.in");
//ofstream cout ("output.out");

ifstream cin ("reguli.in");
ofstream cout ("reguli.out");

static const int NMAX = 5e5+5;

long long v[NMAX];
long long rule[NMAX];
int pi[NMAX];

int getLength (int n) {
	for ( int i = n; i >= 1; --i ) {
		if ( pi[i] && !(i%(i-pi[i])) ) {
			return i-pi[i];
		}
	}
	return 0;
}

void kmp (int n) {
	for ( int i = 2; i < n; ++i ) {
		pi[i] = pi[i-1];

		while ( pi[i] && rule[pi[i]+1] != rule[i] ) {
			pi[i] = pi[pi[i]];
		}

		if ( rule[pi[i]+1] == rule[i] ) {
			pi[i]++;
		}
	}

	int ans = getLength(n);

	cout<<ans<<'\n';
	for ( int i = 1; i <= ans; ++i ) {
		cout<<rule[i]<<'\n';
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int n;
	cin>>n;

	for ( int i = 1; i <= n; ++i ) {
		cin>>v[i];
	}

	for ( int i = 2; i <= n; ++i ) {
		rule[i-1] = v[i]-v[i-1];
	}

	kmp(n);
}