Cod sursa(job #935610)

Utilizator mvcl3Marian Iacob mvcl3 Data 4 aprilie 2013 12:02:29
Problema Reguli Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <fstream>
#include <algorithm>
#define NMAX 500009
#define LL long long
#define i64 64
using namespace std;

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

LL n, X[NMAX], pi[NMAX], el, nr;
char buf[i64];

inline LL get_number() {
    f.getline(buf, i64);
    LL nbr = 0;
    for(char *p = buf; *p; ++p)
        nbr = nbr * 10 + *p - '0';

    return nbr;
}

inline void prefix() {
    int k = 0;
    pi[1] = 0;
    for(int q = 2; q < n; ++q) {
        while(k > 0 && X[k + 1] != X[q])
            k = pi[k];
        if(X[k + 1] == X[q]) ++ k;
        pi[q] = k;
        if(k > 0 && !(q % (q - pi[q])) && nr < q - pi[q]) nr = q - pi[q];
    }
}

int main() {
    f >> n;

    f.getline(buf, i64);

    LL ant = get_number();
    for(int i = 2; i <= n; ++i) {
        el = get_number();
        X[i - 1] = el - ant;
        ant = el;
    }
    reverse(X + 1, X + n);
    prefix();
    if(!nr) nr = n - 1;
    g << nr << '\n';
    for(int i = n - 1; i >= n - nr; --i) g << X[i] << '\n';

    g.close();
    return 0;
}