Cod sursa(job #2985664)

Utilizator MihaiZ777MihaiZ MihaiZ777 Data 26 februarie 2023 19:31:19
Problema Reguli Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <fstream>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

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

const long long LL_INF = 1ll << 62;
const long long INF = 0x3f3f3f3f;

int n;
long long v[500005];
int lps[500005];


int main() {
    fin >> n;
    v[0] = LL_INF;

    long long num, oldNum;
    fin >> num;

    for (int i = 2; i <= n; i++) {
        oldNum = num;
        fin >> num;
        v[i - 1] = num - oldNum;
    }


    // LPS
    int len = n;
    int ans = 0;
    for (int i = 2; i < len; i++) {
        long long currVal = v[i];
        int currIdx = lps[i - 1];

        while (currIdx && currVal != v[currIdx + 1]) {
            currIdx = lps[currIdx];
        }
        if (currVal == v[currIdx + 1]) {
            currIdx++;
        }

        lps[i] = currIdx;

        int periodLen = i - lps[i];
        if (lps[i] && i % periodLen == 0) {
            ans = i;
        }
    }

    int periodLen = -1;
    for (int i = 1; i < len; i++) {
        periodLen = max(periodLen, lps[i]);  
    }

    fout << periodLen << '\n';
    for (int i = 1; i <= periodLen; i++) {
        fout << v[i] << '\n';
    }
}