Cod sursa(job #3163544)

Utilizator andreea_condreaCondrea Andreea andreea_condrea Data 31 octombrie 2023 16:52:08
Problema Reguli Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("reguli.in");
ofstream fout("reguli.out");
vector<int> sol;
int v[500000];
int main()
{
    int k, n, a, b;
    fin>>n;
    fin>>a;
    for(int i=0; i<n-1; i++){
        fin>>b;
        v[i]=b-a;
        a=b;
    }
    n--;
    vector<int> pi(n);
    pi[0]=0;
    k=0;
    for(int i=1; i<n; i++){
        while(k!=0 && v[k]!=v[i])
            k=pi[k-1];
        if(v[k]==v[i])
            k++;
        pi[i]=k;
    }
    fout<<n-pi[n-1]<<'\n';
    for(int i=0; i<n-pi[n-1]; i++)
        fout<<v[i]<<'\n';
    return 0;
}