Cod sursa(job #1633150)

Utilizator roxannemafteiuMafteiu-Scai Roxana roxannemafteiu Data 6 martie 2016 11:40:58
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <fstream>

using namespace std;

const int N_MAX = 5e5;

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

int N;
long long v[N_MAX + 5];
int p[N_MAX + 5];

void read()
{
    fin >> N;
    for(int i = 1; i <= N; ++i)
    {
        fin >> v[i];
        v[i - 1] = v[i] - v[i - 1];
    }
    --N;
}

void compute_prefix()
{
    for(int i = 2, q = 0; i <= N; ++i)
    {
        while(q > 0 && v[q + 1] != v[i])
            q = p[q];
        if(v[q + 1] == v[i])
            ++q;
        p[i] = q;
    }
}

void write()
{
    fout << N - p[N] << "\n";
    for (int i = 1; i <= N - p[N]; ++i)
        fout << v[i] << "\n";
}
int main()
{

    read();
    compute_prefix();
    write();
    return 0;
}