Cod sursa(job #2487913)

Utilizator victorv88Veltan Victor victorv88 Data 5 noiembrie 2019 21:08:14
Problema Reguli Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream f("reguli.in");
ofstream g("reguli.out");

long long n,a, b, dif[500005], ind;
long long prefix[500005];

bool verif(long long indice)
{
    if (prefix[indice])
        return false;
    for (long long i=indice+1; i<=ind; ++i)
    {
        if (prefix[i]<=prefix[i-1])
            return false;
    }
    return true;
}

void create_prefix()
{
    long long poz;
    prefix[1]=0;
    for (long long i=2; i<=ind; ++i)
    {
        poz=prefix[i-1];
        while (poz!=0)
        {
            if (dif[i]==dif[poz+1])
            {
                prefix[i]=poz+1;
                break;
            }
            poz=prefix[poz];
        }
        if (poz==0)
        {
            if (dif[1]==dif[i])
                prefix[i]=1;
            else
                prefix[i]=0;
        }
    }
    long long aux;
    for (long long i=1; i<=ind; ++i)
    {
        if (verif(i))
        {
            cout << i << '\n';
            for (long long j=1; j<=i; j++)
                cout << dif[j] << '\n';
            return;
        }
    }
}

int main( )
{
    f >> n;
    f >> a;
    for (long long i=2; i<=n; ++i)
    {
        f >> b;
        dif[++ind]=b-a;
        a=b;
    }
    create_prefix();
    return 0;
}