Cod sursa(job #2472609)

Utilizator uvIanisUrsu Ianis Vlad uvIanis Data 12 octombrie 2019 17:02:52
Problema Reguli Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <bits/stdc++.h>

using namespace std;

long long a[500005], aux[500005], x_curent, x_anterior, n, pos;

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

    fin >> n;


    fin >> x_anterior >> x_curent;
    a[0] = x_curent - x_anterior;
    x_anterior = x_curent;

    for(long long k = 0, i = 1; i <= n - 2; i++)
    {
        fin >> x_curent;
        a[i] = x_curent - x_anterior;
        x_anterior = x_curent;

        while(k > 0 && a[i] != a[k]) k = aux[k - 1];

        if(a[i] == a[k]) ++k;

        aux[i] = k;
    }

    for(pos = n - 2; pos > 0 && aux[pos] > aux[pos - 1]; --pos );

    ++pos;

    fout << pos << '\n';

    for(long long i = 0; i < pos; ++i) fout << a[i] << '\n';
}