Cod sursa(job #2637097)

Utilizator PatrascuAdrian1Patrascu Adrian Octavian PatrascuAdrian1 Data 21 iulie 2020 11:50:12
Problema Reguli Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <bits/stdc++.h>

using namespace std;

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

const int Nmax = 5e5 + 5;
int N, cat, rest;
int pi[Nmax];
long long delta[Nmax];
long long x, y;

void make_prefix()
{
    int K = 0;

    for(int i = 2; i < N; ++i)
    {
        while(K && delta[K + 1] != delta[i])
            K = pi[K - 1];

        if(delta[K + 1] == delta[i])
            K++;

        pi[i] = K;
    }
}

int main()
{
    in >> N >> x;

    for(int i = 1; i < N; ++i)
    {
        in >> y;
        delta[i] = y - x;
        x = y;
    }

    make_prefix();

    int ans = 0;

    for(int L = 1; L < N && !ans; ++L)
    {
        cat = N / L;
        rest = N % L;

        if(pi[N - rest] &&
                (N - rest) % (N - rest - pi[N - rest]) == 0 &&
                (N - rest) / (N - rest - pi[N - rest]) == cat)
        {
            int k = 1;

            for(int j = N - rest + 1; j < N && k; ++j, ++k)
                if(delta[j] != delta[k])
                    k = 0;

            if(k)
                ans = L;

        }
    }

    out << ans << '\n';

    for(int i = 1; i <= ans; ++i)
        out << delta[i] << '\n';
    return 0;
}