Cod sursa(job #2538247)

Utilizator theo2003Theodor Negrescu theo2003 Data 4 februarie 2020 16:30:34
Problema Reguli Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.83 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;
    int prev_, tmp;
    cin>>prev_;
    n--;
    for(int x = 0;x<n;x++){
        cin>>l[x];
        tmp = l[x];
        l[x] -= prev_;
        prev_ = tmp;
    }
    prefix[0] = 0;
    for(int x = 1, p = 0;x<n;x++){
        if(l[x] == l[p]){
            p++;
            prefix[x] = p;
        }else{
            while(p && (prefix[p] != prefix[x]))
                p = prefix[p - 1];
            if(p)
                p++;
            prefix[x] = p;
        }
    }
    int x = n - prefix[n - 1];
    cout<<x<<'\n';
    for(int y = 0;y<x;y++){
        cout<<l[y]<<'\n';
    }
    return 0;
}