Cod sursa(job #2418130)

Utilizator victoreVictor Popa victore Data 3 mai 2019 19:17:08
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 kb
#include<fstream>
#include<algorithm>

#define ll long long

using namespace std;

const int NMAX = 5e5+5;

ifstream cin("reguli.in");
ofstream cout("reguli.out");

ll x[NMAX],dif[NMAX];
int p[NMAX];

int main()
{
    int N,i,j;

    cin>>N;

    cin>>x[0];

    for(i = 1 ; i < N ; ++i)
    {
        cin>>x[i];
        dif[i-1] = x[i] - x[i-1];
    }

    for(i = 1 , j = 0 ; i <= N-2 ; ++i)
    {
        while(j && dif[i] != dif[j])
            j = p[j-1];

        if(dif[i] == dif[j])
            p[i] = ++j;

    }
    N -= 2;
    int bound = N - p[N] + 1;
    cout<<N - p[N] + 1 << "\n";

    for(i = 0 ; i < bound ; ++i)
        cout<<dif[i] << "\n";

    return 0;
}