Cod sursa(job #2771468)

Utilizator OvidRata Ovidiu Ovid Data 27 august 2021 14:24:29
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll

int n, x[500010];
int dif[500010];
int pi[500010];


void kmp(int pi[], int a[], int n){
pi[0]=0;
for(int i=1, j=pi[0]; i<n; i++){
    while(j>0 && a[j]!=a[i] ){
        j=pi[j-1];
    }
    if(a[j]==a[i]){
        j++;
    }
    pi[i]=j;
}

return;
}



bool check(int k){

vector<int> a;
for(int i=0; i<k; i++){
    a.pb(dif[i]);
}
int x2[n];
x2[0]=x[0];
for(int i=1; i<n; i++){
    x2[i]=x2[i-1]+( a[ (i-1)%k]  );
    if(x2[i]!=x[i]){
        return false;
    }
}
return true;
}


ifstream fin("reguli.in"); ofstream fout("reguli.out");
#define cin fin
#define cout fout



int32_t main(){
INIT
cin>>n;
for(int i=0; i<n; i++){
    cin>>x[i];
}
for(int i=1; i<n; i++){
    dif[i-1]=x[i]-x[i-1];
}
kmp(pi, dif, n-1);
int k=n-1-pi[n-2];
if(check(k)){
    cout<<k<<"\n";
    for(int i=0; i<k; i++){
        cout<<dif[i]<<"\n";
    }
}
else{
    cout<<n-1<<"\n";
    for(int i=0; i<(n-1); i++){
        cout<<dif[i]<<"\n";
    }
}


return 0;
}