Cod sursa(job #3293221)

Utilizator mihail_11Ionescu Mihail mihail_11 Data 10 aprilie 2025 20:15:00
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("reguli.in");
ofstream fout("reguli.out");
int n;
long long int t[500005];
long long int prefix[500005];
long long int dif[500005];
void genpref()
{
    int i,j;
    //cout<<prefix[0]<<' ';
    for(i=1;i<n;++i)///mergem cu i
    {
        j=prefix[i-1];
        while(j>0 && dif[j]!=dif[i])///comparam elementele, nu prefixul
        {
            j=prefix[j-1];
        }
        if(dif[i]==dif[j])
            ++j;
        prefix[i]=j;
        //cout<<prefix[i]<<' ';
    }
}
int main()
{
    int i;
    fin>>n;
    for(i=0;i<n;++i)
    {
        fin>>t[i];///tabloul initial
        //dif[i]=t[i]-t[i-1];
        //cout<<dif[i]<<' ';
    }
    for(i=0;i<n;++i)
    {
        dif[i]=t[i+1]-t[i];
        //cout<<dif[i]<<' ';
    }
    //cout<<'\n';
    genpref();
    fout<<n-1-prefix[n-2]<<'\n';
    for(i=0;i<n-1-prefix[n-2];++i)
    {
        fout<<dif[i]<<'\n';
    }
    return 0;
}