Cod sursa(job #2718838)

Utilizator matei123Biciusca Matei matei123 Data 9 martie 2021 11:39:14
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 f("reguli.in"); ofstream g("reguli.out");
const int Nmax = 5e5 + 5;
int N, cat, rest, pi[Nmax];
long long delta[Nmax], x, y;
void build_kmp()
{   int K = 0;
    for(int i = 2; i < N; ++i)
    {   while(K && delta[K + 1] != delta[i]) K = pi[K - 1];
        if(delta[K + 1] == delta[i]) K++;
        pi[i] = K;
    }
}
int main()
{   f >> N >> x;
    for(int i = 1; i < N; ++i)
    {   f >> y;
        delta[i] = y - x;
        x = y;
    }
    build_kmp();
    int ans = (N - 1) - pi[N - 1];
    g << ans << '\n';
    for(int i = 1; i <= ans; ++i) g << delta[i] << '\n';
    return 0;
}