Cod sursa(job #1726460)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 8 iulie 2016 03:49:10
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;

const int NMAX = 500005;

int p[NMAX];
i64 a[NMAX];

int main(void) {
    freopen("reguli.in",  "r", stdin);
    freopen("reguli.out", "w", stdout);
    int n, q;
    i64 x, y;

    scanf("%d",&n); --n;
    scanf("%lld",&y);
    for(int i=1; i<=n; ++i) {
        x = y;
        scanf("%lld",&y);
        a[i] = y - x;
    }

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

    n-=p[n];

    printf("%d\n",n);
    for(int i=1; i<=n; ++i)
        printf("%lld\n",a[i]);

    fclose(stdin);
    fclose(stdout);
    return 0;
}