Cod sursa(job #2718592)

Utilizator popashtefan10Popa Stefan popashtefan10 Data 8 martie 2021 20:56:19
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <iostream>
#include <cstdio>

using namespace std;

const int NMAX = 500000;

int n;
int dif[NMAX + 5], p[NMAX + 5];

void kmp() {
  p[1] = 0;
  for(int i = 2; i <= n; i++) {
    int crt = p[i - 1];
    while(crt > 0 && dif[crt + 1] != dif[i])
      crt = p[crt];

    p[i] = crt;
    if(dif[i] == dif[crt + 1])
      p[i]++;
  }
}

int main() {
  freopen("reguli.in", "r", stdin);
  freopen("reguli.out", "w", stdout);

  scanf("%d", &n);
  n--;
  for(int i = 0; i <= n; i++)
    scanf("%d", &dif[i]);
  for(int i = n; i; i--)
    dif[i] -= dif[i - 1];

  kmp();

  printf("%d\n", n - p[n]);
  for(int i = 1; i <= n - p[n]; i++)
    printf("%d\n", dif[i]);

  return 0;
}