Cod sursa(job #979148)

Utilizator narcis_vsGemene Narcis - Gabriel narcis_vs Data 31 iulie 2013 21:29:18
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <fstream>

#define In "reguli.in"
#define Out "reguli.out"
#define Nmax 500004
using namespace std;
long long A[Nmax];
int N, PI[Nmax];

inline void Read()
{
    int i, p, x;
    ifstream f(In);
    f>> N >> p;
    for(i = 2;i <= N; ++i,p = x)
    {
        f>>x;
        A[ i - 1 ] = x - p;
    }
    --N;
    f.close();
}

inline void Solve()
{
    int i,k;
    PI[1] = 0;
    for(i = 2;i <= N; i++)
    {
        while(k && A[k+1]!=A[i])
            k = PI[k];
        if(A[k+1]==A[i])
            ++k;
        PI[i]=k;
    }
    N = N-PI[N];
}

inline void Write()
{
    ofstream g(Out);
    int i;
    g<<N<<"\n";
    for(i = 1;i <= N; ++i)
        g<<A[i]<<"\n";
    g.close();
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}