Cod sursa(job #2029121)

Utilizator zdavid112zIon David-Gabriel zdavid112z Data 29 septembrie 2017 13:22:20
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <bits/stdc++.h>

using namespace std;

long long v[500005];
int d[500005];

int main()
{
    freopen("reguli.in", "r", stdin);
    freopen("reguli.out", "w",stdout);
    long long nr, prev, dif;
    int n, k = -1;
    scanf("%d", &n);
    scanf("%lld", &prev);
    scanf("%lld", &nr);
    v[0] = nr - prev;
    d[0] = -1;
    n--;
    prev = nr;
    for(int i = 1; i < n; i++)
    {
        scanf("%lld", &nr);
        dif = nr - prev;
        v[i] = dif;
        while(k != -1 && v[i] != v[k + 1])
            k = d[k];
        if(v[i] == v[k + 1])
            k++;
        d[i] = k;
        prev = nr;
    }
    int lg = n - d[n - 1] - 1;
    printf("%d\n", lg);
    for(int i = 0; i < lg; i++)
        printf("%lld\n", v[i]);
    return 0;
}