Cod sursa(job #2538280)

Utilizator theo2003Theodor Negrescu theo2003 Data 4 februarie 2020 17:00:48
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <fstream>
#include <map>
#include <vector>
using namespace std;
ifstream cin("reguli.in");
ofstream cout("reguli.out");
#define ll long long
ll l[510000], prefix[510000];
int main(){
    ll n;
    cin>>n;
    ll prev_, tmp;
    cin>>prev_;
    n--;
    for(ll x = 0;x<n;x++){
        cin>>l[x];
        tmp = l[x];
        l[x] -= prev_;
        prev_ = tmp;
    }
    prefix[0] = 0;
    for(ll x = 1, p = 0;x<n;x++){
        if(l[x] == l[p]){
            p++;
            prefix[x] = p;
        }else{
            while(p && (l[p] != l[x]))
                p = prefix[p - 1];
            if(l[p] == l[x])
                p++;
            prefix[x] = p;
        }
    }
    ll x = n - prefix[n - 1];
    cout<<x<<'\n';
    for(ll y = 0;y<x;y++){
        cout<<l[y]<<'\n';
    }
    return 0;
}