Cod sursa(job #1975140)

Utilizator MotoAMotoi Alexandru MotoA Data 29 aprilie 2017 23:44:31
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include <fstream>
#include <vector>
using namespace std;
typedef vector <long long> vll;
ifstream f("reguli.in");
ofstream g("reguli.out");
vll dif(1,0),p(500001,0);
int N;
void prefix(){
 int k=0;
 p[1]=0;
 for(int i=2;i<=N;i++){
  while( k && dif[i]!=dif[k+1])k=p[k];
  if(dif[i]==dif[k+1])k++;
  p[i]=k;
 }
}
int main(){
 f>>N;
  N--;
  int x0,x;
  f>>x0;
  for(int i=1;i<=N;i++){
   f>>x;
   dif.push_back(x-x0);
   x0=x;
  }
  prefix();
   int lg=N-p[N];
   g<<lg<<'\n';
  for(vector<long long>::iterator it=dif.begin()+1;it!=dif.begin()+lg+1;it++)
       g<<*it<<'\n';
}