Cod sursa(job #1399906)

Utilizator Mr.DoomRaul Ignatus Mr.Doom Data 24 martie 2015 23:29:29
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <fstream>
using namespace std;

ifstream is("reguli.in");
ofstream os("reguli.out");

const int Nmax = 500001;

long long a[Nmax];
int p[Nmax];
int n;

void Prefix();
void Read();

int main()
{
    Read();
    Prefix();
    os << (n - 1) - p[n - 1] << '\n';
    for ( int i = 1; i <= ((n - 1) - p[n - 1]); ++i )
        os << a[i] << '\n';

    is.close();
    os.close();
    return 0;
}

void Read()
{
    is >> n;
    long long x1, x2;
    is >> x1;
    for ( int i = 1; i < n; ++i )
    {
        is >> x2;
        a[i] = x2 - x1;
        x1 = x2;
    }
}
void Prefix()
{
    int k = 0;
    p[1] = 0;
    for ( int i = 2; i < n; ++i )
    {
        while ( k > 0 && a[k + 1] != a[i] )
            k = p[k];

        if ( a[k + 1] == a[i] )
            ++k;
        p[i] = k;
    }
}