Cod sursa(job #2592799)

Utilizator victorzarzuZarzu Victor victorzarzu Data 2 aprilie 2020 13:21:49
Problema Reguli Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("reguli.in");
ofstream g("reguli.out");
long long dif[500005];
long long x[500005];
int n;
int pi[500005];
vector<long long> res;

void Read()
{
  f>>n;
  for(int i = 1;i <= n;++i)
    f>>x[i];
  for(int i = 1;i < n;++i)
    dif[i] = x[i + 1] - x[i];
}

void compute()
{
  int q = 0;
  for(int i = 2;i < n;++i)
  {
    while(q && dif[q + 1] != dif[i])
      q = pi[q];
    if(dif[q + 1] == dif[i])
      ++q;
    pi[i] = q;
  }
  int length = n - pi[n - 1];
  g<<length<<'\n';
  for(int i = 1;i <= length;++i)
    g<<dif[i]<<'\n';
}

int main()
{
  Read();
  compute();
}