Cod sursa(job #2571268)

Utilizator shantih1Alex S Hill shantih1 Data 4 martie 2020 22:00:53
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <iostream>
#include <fstream>
#include <vector>
#define ll long long

using namespace std;

ifstream fin("reguli.in");
ofstream fout("reguli.out");

int n, i, j;
ll x, y, nr;
vector<ll> v;
vector<int> pi;

void prefix_func() {
  
  pi.resize(v.size());
  pi[1] = 0;
  int k = 0;
  for (int q = 2; q <= n; q++) {
    while (k > 0 && v[k + 1] != v[q])
      k = pi[k];
    if (v[k + 1] == v[q])
      k++;
    pi[q] = k;
  }
}

int main() {
  
  fin >> n;
  fin >> x;
  v.push_back(0);
  for (i = 1; i < n; i++) {
    fin >> y;
    v.push_back(y - x);
    x = y;
  }
  n--;
   
  prefix_func();
  
  int z = n - pi[n];
  fout << z << "\n";
  for (int i = 1; i <= z; i++)
    fout << v[i] << "\n";
}