Cod sursa(job #935614)

Utilizator mvcl3Marian Iacob mvcl3 Data 4 aprilie 2013 12:11:09
Problema Reguli Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 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, poz;
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(pi[q] > nr) nr = pi[q], poz = q;
    }

    if(poz != n - 1) nr = n - 1;
    else nr = poz - pi[poz];
}

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;
    }
    prefix();
    g << nr << '\n';
    for(int i = 1; i <= nr; ++i) g << X[i] << '\n';

    g.close();
    return 0;
}