Cod sursa(job #1755805)

Utilizator ghost24ghost ghost ghost24 Data 11 septembrie 2016 02:43:35
Problema Reguli Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include<iostream>
#include<fstream>
#define DX 500010

using namespace std;
fstream fin("reguli.in",ios::in),fout("reguli.out",ios::out);
long long n,x[DX],a[DX],pre[DX],pozf=1;

void citire();
void scrie();
void mkpre();

int main()
{
    citire();
    mkpre();
    scrie();
}
void scrie()
{
    pozf=n-1;
    fout<<pozf<<"\n";
    for(int i=1;i<=pozf;i++) fout<<a[i]<<"\n";
}

void mkpre()
{
    int i,poz=0;
    for(i=1;i<n;i++)
        a[i]=x[i]-x[i-1];
    for(i=2;i<n;i++)
    {
        while(poz && a[poz+1]!=a[i]) poz=pre[poz];
        if(a[poz+1]==a[i]) poz++;
        pre[i]=poz;
        if(pre[i]==0) pozf=i;
    }
}

void citire()
{
    fin>>n;
    for(int i=0;i<n;i++)
        fin>>x[i];
}