Cod sursa(job #2455849)

Utilizator DavidLDavid Lauran DavidL Data 12 septembrie 2019 21:16:23
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fi("reguli.in");
ofstream fo("reguli.out");

const int NMAX = 5e5 + 5;

int n;
ll x[NMAX], ad[NMAX];
int lsp[NMAX];

void getLsp()
{
    lsp[1] = 0;

    for (int i = 2; i <= n; i++)
    {
        int l = lsp[i - 1];

        while (l > 0 && ad[i] != ad[l + 1])
            l = lsp[l];
        if (ad[i] == ad[l + 1])
            l++;

        lsp[i] = l;
    }
}

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

    for (int i = 1; i < n; i++)
        ad[i] = x[i + 1] - x[i];
    n--;

    getLsp();

    fo << n - lsp[n] << "\n";
    for (int i = 1; i <= n - lsp[n]; i++)
        fo << ad[i] << "\n";

    return 0;
}