Cod sursa(job #2593538)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 4 aprilie 2020 10:02:40
Problema Reguli Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <cstdio>
#include <algorithm>
using namespace std;
const int NMAX = 500000;
const int INF = 2.e9;
long long v[NMAX + 5];
int urm[NMAX + 5] , f[NMAX + 5];
int main()
{
    freopen("reguli.in" , "r" , stdin);
    freopen("reguli.out" , "w" , stdout);
    int n , i , k , l;
    scanf("%d" , &n);
    for(i = 0 ; i < n ; i ++)
        scanf("%lld" , &v[i]);
    for(i = n - 1 ; i >= 1 ; i --)
        v[i] = v[i] - v[i - 1];
    urm[1] = k = 0;
    for(i = 2 ; i < n ; i ++)
    {
        while(k > 0 && v[k + 1] != v[i])
            k = urm[k];
        if(v[k + 1] == v[i])
            k ++;
        urm[i] = k;
        if(k > 0 && v[k] == v[i] && k % (i - k) == 0)
            f[i - k] ++;
    }
    l = 0;
    for(i = 1 ; i < n && !l ; i ++)
        if(((n - 1) / i - 1) == f[i])
            l = i;
    printf("%d\n" , l);
    for(i = 1 ; i <= l ; i ++)
        printf("%lld\n" , v[i]);
    return 0;
}