Cod sursa(job #2725281)
Utilizator | Data | 18 martie 2021 18:31:07 | |
---|---|---|---|
Problema | Reguli | Scor | 80 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 0.69 kb |
#include <fstream>
using namespace std;
ifstream in("reguli.in");
ofstream out("reguli.out");
const int N = 5e5;
long long dif[N+2];
int lps[N+2];
int main()
{
int n;
in>>n;
int x;
in>>x;
--n;
for(int i=1;i<=n;++i){
int y;
in>>y;
dif[i]=y-x;
x=y;
}
lps[1]=0;
int len=0,lmax=0;
for(int i=2;i<=n;++i){
while(len && dif[i]!=dif[len+1]){
len=lps[len-1];
}
if(dif[len+1]==dif[i]){
++len;
}
lps[i] = len;
}
lmax = n-lps[n];
out<<lmax<<'\n';
for(int i=1;i<=lmax;++i){
out<<dif[i]<<'\n';
}
return 0;
}