Pagini recente » Rating Falticeanu Dumitru-Paul (ecstazi) | Cod sursa (job #2985664)
#include <fstream>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
ifstream fin("reguli.in");
ofstream fout("reguli.out");
const long long LL_INF = 1ll << 62;
const long long INF = 0x3f3f3f3f;
int n;
long long v[500005];
int lps[500005];
int main() {
fin >> n;
v[0] = LL_INF;
long long num, oldNum;
fin >> num;
for (int i = 2; i <= n; i++) {
oldNum = num;
fin >> num;
v[i - 1] = num - oldNum;
}
// LPS
int len = n;
int ans = 0;
for (int i = 2; i < len; i++) {
long long currVal = v[i];
int currIdx = lps[i - 1];
while (currIdx && currVal != v[currIdx + 1]) {
currIdx = lps[currIdx];
}
if (currVal == v[currIdx + 1]) {
currIdx++;
}
lps[i] = currIdx;
int periodLen = i - lps[i];
if (lps[i] && i % periodLen == 0) {
ans = i;
}
}
int periodLen = -1;
for (int i = 1; i < len; i++) {
periodLen = max(periodLen, lps[i]);
}
fout << periodLen << '\n';
for (int i = 1; i <= periodLen; i++) {
fout << v[i] << '\n';
}
}