Cod sursa(job #2979605)

Utilizator raresgherasaRares Gherasa raresgherasa Data 15 februarie 2023 17:00:34
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <bits/stdc++.h>

using namespace std;

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

const int kN = 1e6 + 5;

long long a[kN], n, x;
int z[kN];

int main(){
   ios_base::sync_with_stdio(false);

   fin >> n >> x;
   for (int i = 0; i < n - 1; i++){
      long long y; fin >> y;
      a[i] = y - x;
      x = y;
   }
   --n;
   int l = 0, r = 0;
   for (int i = 1; i < n; i++){
      if (i <= r){
         z[i] = min(z[i - l], r - i + 1);
      }
      while (i + r < n && a[z[i]] == a[z[i] + i]){
         ++z[i];
      }
      if (i + z[i] - 1 > r){
         l = i;
         r = i + z[i] - 1;
      }
   }
   int ans = n;
   for (int i = 0; i < n; i++){
      if (i + z[i] == n){
         ans = i;
         break;
      }
   }
   fout << ans << '\n';
   for (int i = 0; i < ans; i++){
      fout << a[i] << '\n';
   }
}