Cod sursa(job #2058804)

Utilizator CammieCamelia Lazar Cammie Data 6 noiembrie 2017 10:20:08
Problema Reguli Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <fstream>

#define MAXN 500002

using namespace std;

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

int pi[MAXN], maxim, N;
long long v[MAXN];

inline void Read() {
    long long ante, curent;

    fin >> N; fin >> ante;

    for (int i = 1; i < N; i++) {
        fin >> curent;

        v[i] = (long long)(curent - ante);
        ante = curent;
    }
    N--;
}

inline void Det_pi() {
    int k = 0; pi[1] = 0;

    for (int i = 2; i <= N; i++) {
        while (k > 0 && v[i] != v[k + 1])
            k = pi[k];

        if (v[i] == v[k + 1])
            k++;

        pi[i] = k;

        if (k - pi[k] > maxim)
            maxim = k - pi[k];
    }
}

inline void Afisare() {
    fout << maxim << "\n";

    for (int i = 1; i <= maxim; i++)
        fout << v[i] << "\n";
}

int main () {
    Read();
    Det_pi();
    Afisare();

    fin.close(); fout.close(); return 0;
}