Cod sursa(job #2592795)

Utilizator victorzarzuZarzu Victor victorzarzu Data 2 aprilie 2020 13:19:43
Problema Reguli Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 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;
  }
  if(pi[n - 1] == 0)
    {
      g<<n - 1<<'\n';
      for(int i = 1;i < n;++i)
        g<<dif[i]<<'\n';
    }
  else
  {
    for(int i = 1;i < n && pi[i] == 0;++i)
      res.push_back(dif[i]);
    g<<res.size()<<'\n';
    for(vector<long long>::iterator it = res.begin();it != res.end();++it)
     g<<*it<<'\n';
  }
}

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