Cod sursa(job #3225807)

Utilizator paull122Paul Ion paull122 Data 18 aprilie 2024 23:01:16
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>

#define NMAX 500000
#define LOG 21
#define INF (int)(10e8)
#define MOD 1000000007
#define ll  long long int


using namespace std;
ifstream fin("reguli.in");
ofstream fout("reguli.out");

int z[NMAX+1];
ll a[NMAX+1];
int n;

ll d[NMAX+1];

void computeZ()
{
    int l=0,r=0;
    for(int i=1;i<n-1;i++)
    {
        if(i<r)
        {
            z[i] = min(r-i,z[i-l]);
        }
        while(i+z[i] < n-1 && d[z[i]+i] == d[z[i]])
        {
            ++z[i];
        }
        if(i+z[i] > r)
        {
            r=i+z[i];
            l=i;
        }
    }
}
int main()
{
    fin >> n;
    for(int i=0;i<n;i++)
    {
        fin >> a[i];
    }
    for(int i=1;i<n;i++)
    {
        d[i-1] = a[i]-a[i-1];
    }
    computeZ();
    int res=0;
    for(int i=1;i<n-1 && !res;i++)
    {
        if(z[i]+i==n-1)
        {
            res=i;
        }
    }
    if(!res)
    {
        fout << n-1 << "\n";
        for(int i=0;i<n-1;i++)
        {
            fout << d[i] << "\n";
        }
        return 0;
    }
    fout << res << "\n";
    for(int i=0;i<res;i++)
    {
        fout << d[i] << "\n";
    }
}