Cod sursa(job #2637098)

Utilizator PatrascuAdrian1Patrascu Adrian Octavian PatrascuAdrian1 Data 21 iulie 2020 11:51:40
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <bits/stdc++.h>

using namespace std;

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

const int Nmax = 5e5 + 5;
int N, cat, rest;
int pi[Nmax];
long long delta[Nmax];
long long x, y;

void make_prefix()
{
    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()
{
    in >> N >> x;

    for(int i = 1; i < N; ++i)
    {
        in >> y;
        delta[i] = y - x;
        x = y;
    }

    make_prefix();

    int ans = (N - 1) - pi[N - 1];

    out << ans << '\n';

    for(int i = 1; i <= ans; ++i)
        out << delta[i] << '\n';
    return 0;
}