Cod sursa(job #2006902)

Utilizator Mircea_DonciuDonciu Mircea Mircea_Donciu Data 1 august 2017 11:52:27
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include<fstream>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define sz size
#define pb push_back
#define mp make_pair
#define bg begin
#define nd end
using namespace std;

#define int long long

const int maxn = 500003;
const int maxk = 1003;

int pref[maxn];
int arr[maxn];
int n;
void kmp(){

    int q = 0;
    pref[1] =0;
    for(int i=2;i<n;i++){

        while(q && arr[q+1]!=arr[i]){
            q = pref[q];
        }
        if(arr[q+1] == arr[i]) q++;

        pref[i] = q;
    }
}
int32_t main()
{
    ifstream f("reguli.in");
    ofstream g("reguli.out");
    ios_base::sync_with_stdio(false);
    f>> n;
    int x,bef;
    for(int i=0;i<n;i++){
        f>> x;
        if(i > 0){
            arr[i] = x - bef;
        }
        bef = x;
    }
    kmp();
    g<< n-pref[n-1] - 1 << '\n';
    for(int i=1;i<n-pref[n-1];i++){
        g<< arr[i] << '\n';
    }
    return 0;
}