Cod sursa(job #3321748)

Utilizator brianabucur11Briana Bucur brianabucur11 Data 11 noiembrie 2025 10:24:57
Problema Reguli Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 5e5 + 5;

int n, v[nmax], lps[nmax];

signed main()
{
    fin >> n;
    vector <int> v(n);
    for (int i = 0; i < n; i++)
        fin >> v[i];
    for (int i = n - 1; i >= 1; i--)
        v[i] -= v[i - 1];
    v[0] = 0;
    v.erase(v.begin());
    n--;
    int k = 0;
    for (int i = 1; i < n; i++)
    {
        while (k != 0 && v[i] != v[k])
            k = lps[k-1];
        if (v[i] == v[k])
            k++;
        lps[i] = k;
    }
    if (lps[n - 1] == 0)
    {
        fout << n << '\n';
        for (int i = 0; i < n; i++)
            fout << v[i] << '\n';
        return 0;
    }
    int rez = n - lps[n - 1];
    fout << rez << '\n';
    for (int i = 0; i < rez; i++)
        fout << v[i] << '\n';
    return 0;
}