Cod sursa(job #2063168)

Utilizator netfreeAndrei Muntean netfree Data 11 noiembrie 2017 10:01:05
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const ll N_MAX = 500000 + 5;

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

ll n, x, v[N_MAX];
ll key[N_MAX];

ll k_max = 0;

ll build_key(){
    ll k = 0;
    for(ll i = 2; i<=n; ++i){
        while(k > 0 and v[k+1] != v[i])
            k = key[k];
        if(v[k+1] == v[i])
            k ++;
        key[i] = k;
    }

    for(ll i = n; i>=1; --i)
        if(key[i] == 0)
            return i;

//    for(ll i = 1; i<=n; ++i)
//        cout << key[i] << " ";
}

int main()
{
    fin >> n >> x;
    n--;
    for(ll i = 1, y; i<=n; ++i){
        fin >> y;
        v[i] = y - x;
        x = y;
    }

//    for(ll i = 1; i<=n; ++i)
//        cout << v[i] << " ";

    ll aux = build_key();

    aux = n - key[n];

    fout << aux << "\n";
    for(ll i = 1; i<=aux; ++i)
        fout << v[i] << "\n";

    return 0;
}