Cod sursa(job #2262050)

Utilizator NToniBoSSNicolae Tonitza NToniBoSS Data 16 octombrie 2018 21:58:50
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <bits/stdc++.h>

using namespace std;

long long v[500001];

int pee[500001];

int main()

{

    int n,i,k,rez;

    long long x,y;

    ios::sync_with_stdio(false);

    ifstream in("reguli.in");

    ofstream out("reguli.out");

    in>>n>>x;

    for(i=2; i<=n; i++)

    {

        in>>y;

        v[i-1]=y-x;

        x=y;

    }

    n--;

    k=0;

    for(i=2; i<=n; i++)

    {

        while(k && v[k+1]!=v[i])

            k=pee[k];

        if(v[k+1]==v[i])

            ++k;

        pee[i]=k;

    }

    rez=0;

    for(i=2; i<=n; i++)

        if(i%(i-pee[i])==0 && pee[i] && n-i<i-pee[i])

            rez=i-pee[i];

    if(!rez)

        rez=n;

    out<<rez<<"\n";

    for(i=1; i<=rez; i++)

        out<<v[i]<<"\n";



    return 0;

}