Cod sursa(job #2261981)

Utilizator NToniBoSSNicolae Tonitza NToniBoSS Data 16 octombrie 2018 21:09:46
Problema Reguli Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <bits/stdc++.h>
using namespace std;
int v[500001],pee[500001];
int main()
{
    int n,x,y,i,k,rez;
    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];
    out<<rez<<"\n";
    for(i=1; i<=rez; i++)
        out<<v[i]<<"\n";

    return 0;
}