Cod sursa(job #2900520)

Utilizator MihneaCadar101Cadar Mihnea MihneaCadar101 Data 11 mai 2022 00:14:09
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <bits/stdc++.h>
using namespace std;

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

const int nmax = 5e5 + 5;

long long n, v[nmax], aux[nmax], total, pre[nmax];

void preprocess() {
    int i = 1, len = 0;
    while (i <= total) {
        if (aux[i] == aux[len]) {
            ++len;
            pre[i] = len;
            ++i;
        }
        else {
            if (len)
                len = pre[len - 1];
            else {
                pre[i] = 0;
                ++i;
            }
        }
    }
}

int main()
{
    fin >> n;
    for (int i = 1; i <= n; ++i)
        fin >> v[i];

    for (int i = 2; i <= n; ++i)
        aux[i - 2] = v[i] - v[i - 1];

    total = n - 2;
    preprocess();
    long long maxi = 0;
    for (int i = 0; i <= total; ++i) {
        if (pre[i] > maxi)
            maxi = pre[i];
    }

    while (total >= 0 && maxi && pre[total] == maxi) {
        --total;
        --maxi;
    }

    fout << total + 1 << '\n';
    for (int i = 0; i <= total; ++i)
        fout << aux[i] << '\n';

    return 0;
}