Cod sursa(job #2717461)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 7 martie 2021 14:26:45
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <bits/stdc++.h>

#define NMAX 500005
using namespace std;

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

long long v[NMAX], dif[NMAX], pi[NMAX];

int main()
{
    int n;
    fin >> n;

    for(int i = 1; i <= n; ++i)
        fin >> v[i];

    for(int i = 1; i < n; ++i)
        dif[i] = v[i + 1] - v[i];

    int q = 0;
    for(int i = 2; i < n; ++i){
        while(q && dif[q + 1] != dif[i])
            q = pi[q];
        if(dif[q + 1] == dif[i])
            ++q;
        pi[i] = q;
    }

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