Cod sursa(job #1819092)

Utilizator dungdxhpDONG XUAN DUNG dungdxhp Data 30 noiembrie 2016 10:18:21
Problema Reguli Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <bits/stdc++.h>
#define forinc(i, j, k) for(int i = j; i <= k; ++i)
#define nn 500001
#define ll long long

using namespace std;

ll x[nn], a[nn];int nxt[nn];
int n, result;

int read()
{
    ll res = 0;
    char c = getchar();
    while(c < '0'|| c > '9') c = getchar();
    for(; c >='0' && c <='9'; c = getchar()) res = res * 10 + c - '0';
    return res ;
}

int main()
{
    freopen("reguli.in", "r", stdin);
    freopen("reguli.out", "w", stdout);
    n = read();
    forinc(i, 1, n)
    {
        x[i] = read();
    }

    forinc(i, 2, n) a[i - 1] = x[i] - x[i - 1] ;
    //forinc(i, 1, n) cout << a[i]<<endl;
    nxt[1] = 0 ; int j = 0 ;
    forinc(i, 2, n-1)
    {
        while(j != 0 && a[i] != a[j + 1]) j = nxt[j];
        if (a[i] == a[j + 1])
        {
            ++j;
            nxt[i] = j;
        }
        else nxt[i] = 0;
    }

    result = n - 1 - nxt[n - 1];
    cout << result<<endl;
    forinc(i, 1, result) cout << a[i]<< endl;
}