Cod sursa(job #3161722)

Utilizator Maftei_TudorMaftei Tudor Maftei_Tudor Data 27 octombrie 2023 19:53:09
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <fstream>

using namespace std;
ifstream in("reguli.in");
ofstream out("reguli.out");
const int N = 5e5 + 5;

long long n, x, y, v[N], pi[N];

int main() {
    in >> n;
    in >> x;
    for(int i=1; i<n; i++) {
        in >> y;
        v[i-1] = y - x;
        x = y;
    }

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

        while(j && v[i] != v[j])
            j = pi[j-1];
        
        if(v[i] == v[j])
            j++;
        pi[i] = j;
    }

    int ans = n - 1 - pi[n-1] + 1;
    out << ans << '\n';
    for(int i=0; i<ans; i++)
        out << v[i] << '\n';
    return 0;
}