Cod sursa(job #2636878)

Utilizator PatrascuAdrian1Patrascu Adrian Octavian PatrascuAdrian1 Data 20 iulie 2020 15:11:00
Problema Reguli Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <bits/stdc++.h>

using namespace std;

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

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

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)
            ans = L;
    }

    out << ans << '\n';

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