Pagini recente » Cod sursa (job #1882074) | Cod sursa (job #2437980) | Cod sursa (job #2793344) | Cod sursa (job #2488092) | Cod sursa (job #856645)
Cod sursa(job #856645)
#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("reguli.in");
ofstream fout("reguli.out");
typedef long long int64;
const int MAX_N = 500100;
int v[MAX_N];
int prefix[MAX_N];
int N, K;
void read(), solve(), print();
void compute_prefix(int* pattern);
int main() {
read();
solve();
print();
return 0;
}
void read() {
fin >> N;
--N;
for (int i = 0; i <= N; ++i) {
fin >> v[i];
}
}
void solve() {
for (int i = N; i > 0; --i) {
v[i] -= v[i-1];
}
compute_prefix(v);
K = N - prefix[N];
}
void compute_prefix(int* pattern) {
prefix[1] = 0;
int p = 0;
for (int i = 2; i <= N; ++i) {
while (p > 0 && pattern[p+1] != pattern[i]) p = prefix[p];
if (pattern[p+1] == pattern[i]) ++p;
prefix[i] = p;
}
}
void print() {
fout << K << '\n';
for (int i = 1; i <= K; ++i) {
fout << v[i] << '\n';
}
}