Cod sursa(job #2629232)

Utilizator iulianarsenoiuArsenoiu Iulian iulianarsenoiu Data 19 iunie 2020 16:41:53
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("reguli.in");
ofstream g("reguli.out");
int n,z[500005];
long long v[500005];
void Z()
{
    for(int i=2,l=0,r=0;i<=n;i++)
    {
        if(i<=r)
        {
            z[i]=min(z[i-l],r-i+1);
        }
        while(i+z[i]<=n && v[z[i]+1]==v[i+z[i]])
        {
            z[i]++;
        }
        if(i+z[i]-1>r)
        {
            l=i;
            r=i+z[i]-1;
        }
    }
}
int main()
{
    f>>n;
    n--;
    for(int i=0;i<=n;i++)
    {
        f>>v[i];
    }
    for(int i=n;i>=1;i--)
    {
        v[i]-=v[i-1];
    }
    v[0]=0;
    Z();
    for(int i=1;i<=n;i++)
    {
        if(z[i]==n-i+1)
        {
            g<<i-1<<'\n';
            for(int j=1;j<i;j++)
            {
                g<<v[j]<<'\n';
            }
            return 0;
        }
    }
    g<<n<<'\n';
    for(int i=1;i<=n;i++)
    {
        g<<v[i]<<'\n';
    }
    return 0;
}