Cod sursa(job #1188351)

Utilizator cruelifanLouis Cypher cruelifan Data 19 mai 2014 14:29:16
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <fstream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

const int knmax = 5e5 + 5;

long long n, szans, gv[knmax], ans[knmax], t[knmax];

void prefix(){
  int p = 0;
  t[0] = 0;
  for(int i = 2; i < n; ++i){
    p = i - 1;
    do{
      p = t[p];
      if(gv[p + 1] == gv[i]){
        t[i] = p + 1;
        break;
      }
    }while(p);
  }
}

void solve(){
  prefix();

  szans = n - t[n - 1] - 1;
  for(int i = 0; i < szans; ++i)
    ans[i] = gv[i + 1];
}

int main(){
  ifstream in("reguli.in");
  ofstream out("reguli.out");

  in >> n;
  long long x, y;
  in >> x;
  for(int i = 1; i < n; ++i){
    in >> y;
    gv[i] = y - x;
    x = y;
  }

  in.close();

  solve();

  out << szans << "\n";
  for(int i = 0; i < szans; ++i)
    out << ans[i] << "\n";

  out.close();

  return 0;
}