Cod sursa(job #2242379)

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

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

int nums[NMAX], prefix[NMAX];
vector<int> max_seq;
int n;

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(int nums[], int 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;
    }
}

void return_max_seq(int nums[], int v[], int n, vector<int>& elems){
    int maxim = v[1];
    int pos = 1;
    for(int i = 2; i<=n; i++){
        if(maxim < v[i]){
            maxim = v[i];
            pos = i;
        }
    }
    for(int i = pos - maxim + 1; i<=pos; i++){
        elems.push_back(nums[i]);
    }
}

int main(){
    int p;
    read_data(p);
    construct_prefix(nums, prefix, p);
    return_max_seq(nums, prefix, p, max_seq);
    int pos = 0;
    while(pos < max_seq.size()){
        if(max_seq[pos] == max_seq[max_seq.size() - 1]){
            pos ++;
            max_seq.pop_back();
        }else{
            break;
        }
    }
    out << max_seq.size() << '\n';
    for(const auto& elem : max_seq){
        out << elem <<'\n';
    }
    return 0;
}