Cod sursa(job #3323082)

Utilizator Radu_BicliBiclineru Radu Radu_Bicli Data 16 noiembrie 2025 22:29:40
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.65 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("reguli.in");
ofstream fout("reguli.out");
long long n, i, j, x[500002], lpf[500002];

int main() {
    //ios_base::sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);

    fin >> n;
    for(i = 1; i <= n; i++) fin >> x[i];
    for(i = 1; i <  n; i++) x[i] = x[i + 1] - x[i];

    n--;
    j = 0;
    for(i = 2; i <= n; i++) {
        while(j > 0 && x[i] != x[j + 1]) j = lpf[j - 1];
        if(x[i] == x[j + 1]) j++;
        lpf[i] = j;
    }

    fout << n - lpf[n] << "\n";
    for(i = 1; i <= n - lpf[n]; i++) fout << x[i] << "\n";

    return 0;
}