Cod sursa(job #2985697)

Utilizator MihaiZ777MihaiZ MihaiZ777 Data 26 februarie 2023 20:28:58
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 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];

void BuildLPS() {
    int len = n;
    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];
    }
}

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;
    }

    BuildLPS();
    
    int ans = n  - lps[n - 1] - 1;
    fout << ans << '\n';
    for (int i = 1; i <= ans; i++) {
        fout << v[i] << '\n';
    }
}