Cod sursa(job #3161670)

Utilizator ililogIlinca ililog Data 27 octombrie 2023 19:15:46
Problema Reguli Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
using namespace std;
#include<iostream>
#include<fstream>

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

int n;
int a[500001];
int v[500000];
int lps[500001];

int main() {
    
    fin >> n;
    for (int i = 1; i<=n; i++) {
        fin >> a[i];
    }
    
    for (int i = 1; i<n; i++) {
        v[i] = a[i+1] - a[i];
       // cout << v[i] << " ";
    }
    
    //cout << "\n0 "; 
    int j = 0;
    int maxim = 0, pozmax = 0;
    for (int i = 2; i<n; i++) {
        while (j != 0 && v[j+1] != v[i]) {
            j = lps[j+1];
        }
        if (v[j+1] == v[i]) {
            j++;
        }
        lps[i] = j;
     //   cout << lps[i] << " ";
        if (j > 0 && i % (i-j) == 0) {
            if (maxim < i-j) {
                maxim = i-j;
                pozmax = i;
            }
        }
    }
    
    fout << maxim << "\n";
    
    for (int i = pozmax-maxim+1; i<=pozmax; i++) {
        fout << v[i] << "\n";
    }
    
    return 0;
}