Cod sursa(job #3167863)

Utilizator IvanAndreiIvan Andrei IvanAndrei Data 11 noiembrie 2023 10:41:06
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <bits/stdc++.h>

using namespace std;

const long long max_size = 5e5 + 1;

long long v[max_size], p[max_size];

void kmp (long long n)
{
    long long q = 0;
    for (long long i = 2; i <= n; i++)
    {
        while (q > 0 && v[q + 1] != v[i])
        {
            q = p[q];
        }
        if (v[q + 1] == v[i])
        {
            q++;
        }
        p[i] = q;
    }
}

signed main ()
{
    #ifdef LOCAL
       freopen("test.in", "r", stdin);
       freopen("test.out", "w", stdout);
    #else
       freopen("reguli.in", "r", stdin);
       freopen("reguli.out", "w", stdout);
    #endif // LOCAL
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    long long ult, n;
    cin >> n >> ult;
    n--;
    for (long long i = 1; i <= n; i++)
    {
        long long x;
        cin >> x;
        v[i] = x - ult;
        ult = x;
    }
    kmp(n);
    long long per = n - p[n];
    cout << per << '\n';
    for (long long i = 1; i <= per; i++)
    {
        cout << v[i] << '\n';
    }
    return 0;
}