Pagini recente » Profil Tghica | Monitorul de evaluare | Cod sursa (job #1144331) | Cod sursa (job #1088940) | Cod sursa (job #17044)
Cod sursa(job #17044)
// O(N) time and memory
#include <stdio.h>
#include <assert.h>
#define ll long long
#define NMax 500005
int N;
ll v[NMax]; int pi[NMax], ok[NMax];
void functie_prefix(void)
{
int i, k;
pi[1] = 0; k = 0;
for (i = 2; i <= N; i++)
{
while (k > 0 && v[k+1] != v[i])
k = pi[k];
if (v[k+1] == v[i])
k++;
pi[i] = k;
}
}
int main(void)
{
int i, K, c, r, sol = 0;
ll x, ant;
freopen("reguli.in", "r", stdin);
freopen("reguli.out", "w", stdout);
scanf("%d", &N);
assert(5 <= N && N <= 500000);
scanf("%I64d", &ant);
for (i = 2; i <= N; i++)
{
scanf("%I64d", &x);
v[i-1] = x-ant;
ant = x;
}
N--;
functie_prefix();
for (r = N; r; r = pi[r])
ok[pi[r]] = 1;
for (K = 1; K <= N; K++)
{
c = N / K; r = N % K;
if (pi[N-r] > 0 && (N-r) % (N-r-pi[N-r]) == 0 &&
(N-r) / (N-r-pi[N-r]) == c && ok[r])
{ sol = 1; break; }
}
if (!sol) K--;
printf("%d\n", K);
for (i = 1; i <= K; i++)
printf("%I64d\n", v[i]);
return 0;
}