Pagini recente » Cod sursa (job #278650) | Cod sursa (job #2258001) | Cod sursa (job #133844) | Cod sursa (job #2804069) | Cod sursa (job #2242379)
#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;
}