Cod sursa(job #2630195)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 24 iunie 2020 17:15:49
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <fstream>

using namespace std;

ifstream f ("reguli.in");
ofstream g ("reguli.out");

constexpr int NMAX = 5e5 + 5;

long long dif[NMAX];
int phi[NMAX];
int N;

void Read ()
{
    long long old_x = 0;
    f >> N >> old_x;

    for (int i = 1; i < N; ++ i ) {
        long long x; f >> x;
        dif[i-1] = x - old_x;
        old_x = x;
    }
    --N;
}

void Construire_PHI ()
{
    int rez = 0;
    for (int i = 1; i < N; ++ i ) {
        while (rez > 0 && dif[ i ] != dif[ rez ]) {
            rez = phi[rez - 1];
        }
        if (dif[ i ] == dif[ rez ]) ++ rez;
        phi[i] = rez;
    }
}

int main()
{
    Read();
    Construire_PHI();

    int ans = N - phi[N-1];
    g << ans << '\n';
    for (int i = 0; i < ans; ++ i ) {
        g << dif[i] << '\n';
    }

    return 0;
}