Cod sursa(job #2242383)

Utilizator GeorgianBaditaBadita Marin-Georgian GeorgianBadita Data 18 septembrie 2018 17:03:58
Problema Reguli Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <fstream>
#include <vector>
#define NMAX 500005
using namespace std;

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

long long nums[NMAX], prefix[NMAX];
int n;
long long ak;

void read_data(int &p){
    p = 0;
    int x, y;
    in >> n >> x;
    for(int i = 0; i<n; i++){
        in >> y;
        nums[++p] = y - x;
        x = y;
    }
    p --;
}

void construct_prefix(long long nums[], long long v[], int n){
    int k = 0;
    v[1] = 0;
    for(int i = 2; i<=n; i++){
        while(k > 0 && nums[i] != nums[k + 1]){
            k = v[k];
        }
        if(nums[k + 1] == nums[i]){
            k ++;
        }
        v[i] = k;
    }
    ak = n - 1 - v[n - 1];
}


int main(){
    int p;
    read_data(p);
    construct_prefix(nums, prefix, p);
    out << ak << '\n';
    for(int i =1 ; i<=ak; i++){
        out << nums[i] << '\n';
    }
    return 0;
}