Cod sursa(job #1759942)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 20 septembrie 2016 00:44:07
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <bits/stdc++.h>

using namespace std;
int N;
int A[500005];
int P[500005];

void read()
{
    scanf("%d", &N);
    for (int i = 1; i <= N; ++i)
        scanf("%d", &A[i]);
    for (int i = 1; i < N; ++i)
        A[i] = A[i+1] - A[i];
    --N;
}

void make_prefix()
{
    int q = 0;
    for (int i = 2; i <= N; ++i) {
        while (q && A[q + 1] != A[i])
            q = P[q];
        q += A[q + 1] == A[i];
        P[i] = q;
    }
}

int main()
{
    freopen("reguli.in","r",stdin);
    freopen("reguli.out","w",stdout);

    read();
    make_prefix();
    printf("%d\n", N - P[N]);
    for (int i = 1; i <= N - P[N]; ++i)
        printf("%d\n", A[i]);

    return 0;
}