Cod sursa(job #3309293)

Utilizator calinarulMarinescu Calin calinarul Data 3 septembrie 2025 14:08:29
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <bits/stdc++.h>
#define int long long
using  namespace std;
ifstream fin("reguli.in");
ofstream fout("reguli.out");
const int NMAX=5*1e5+5;
int x[NMAX];
int lps[NMAX];
vector<int>diff;
void prebuilt(vector<int>pattern)
{
    int i=1;
    int m=pattern.size();
    int lenght=0;
    lps[0]=0;
    while(i<m)
    {
        if(pattern[i]==pattern[lenght])
        {
            lenght++;
            lps[i]=lenght;
            i++;
        }
        else
        {
            if(lenght!=0)lenght=lps[lenght-1];
            else {lps[i]=0;i++;}
        }
    }
}
signed main()
{
    int n;
    fin>>n;
    for(int i=1;i<=n;i++)fin>>x[i];
    for(int i=1;i<n;i++)diff.push_back(x[i+1]-x[i]);
    prebuilt(diff);
    int ans=diff.size()-lps[diff.size()-1];
    if(diff.size()==1){fout<<"1\n";return 0;}
    // if(ans==0)ans=diff.size();
    fout<<ans<<'\n';
    for(int i=0;i<ans;i++)
    fout<<diff[i]<<'\n';
}