Cod sursa(job #2717293)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 6 martie 2021 23:42:41
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <bits/stdc++.h>
#define int long long

using namespace std;

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

vector<int> preffix_function(const vector<int> &A) {
    vector<int> pi(A.size());
    int N = A.size() - 1;
    for(int i = 2, q = 0; i <= N; ++i) {
        while(q && A[q + 1] != A[i])
            q = pi[q];
        if(A[q + 1] == A[i])
            ++q;
        pi[i] = q;
    }
    return pi;
}

int32_t main() {
    int N, prv;
    fin >> N >> prv;
    vector<int> a{0};
    for(int i = 2; i <= N; ++i) {
        int x;
        fin >> x;
        a.emplace_back(x - prv);
        prv = x;
    }
    vector<int> pi = preffix_function(a);
    N = a.size() - 1;
    fout << N - pi[N] << '\n';
    for(int i = 1; i <= N - pi[N]; ++i)
        fout << a[i] << '\n';
}