Cod sursa(job #1894949)

Utilizator LolkekzorChiorean Tudor Lolkekzor Data 27 februarie 2017 18:05:56
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <fstream>
using namespace std;

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

int n, x, y, i, j, lun;
int v[ 500010 ], T[ 500010 ];

int main()
{
    fin >> n;
    fin >> x;
    for ( i = 1 ; i < n ; i++ ) {
        fin >> y;
        v[ i - 1 ] = y - x;
        x = y;
    }

    lun = n - 1;
    i = 1; j = 0;
    while ( i < lun ) {
        if ( v[ i ] == v[ j ] ) {
            T[ i ] = j + 1;
            i++; j++;
        } else if ( j != 0 ) {
            while ( j != 0 && v[ i ] != v[ j ] )
                j = T[ j - 1 ];
        } else {
            i++;
        }
    }

    fout << lun - T[ lun - 1 ] << '\n';
    for ( i = 0 ; i < lun - T[ lun - 1 ] ; i++ ) {
        fout << v[ i ] << '\n';
    }

    return 0;
}