Mickey Mouse Constructive

Prefix Sums Are The Whole Game

Let

$$P_0=0,\qquad P_i=\sum_{j=1}^{i} a_j.$$

The total sum is

$$S=P_n=x-y.$$

Suppose we split the array into $k$ subarrays, all with the same sum $q$. Then

$$kq=S.$$

So if $S\ne 0$, $q$ is completely tied to a divisor of $S$. More precisely, $|q|$ is a positive divisor of $|S|$. That already smells like the answer is going to be a divisor count, because yes, this problem is wearing a constructive mask over a tiny number theory face.

The Forced Lower Bound

Assume $S>0$ first. Pick any positive divisor $d$ of $S$. Since every array element is either $1$ or $-1$, the prefix sum changes by exactly $1$ in absolute value each step. A walk starting at $0$ and ending at $S$ cannot jump over $d,2d,3d,\ldots,S$.

So there exist indices

$$0=t_0<t_1<t_2<\cdots<t_{S/d}=n$$

such that

$$P_{t_j}=jd.$$

Then every segment has sum

$$P_{t_j}-P_{t_{j-1}}=d.$$

That is one valid partition for this divisor $d$. Different divisors give different block sums, hence different partition types. Therefore, for every possible ordering,

$$f(a)\ge \tau(S),$$

where $\tau(m)$ is the number of positive divisors of $m$.

For $S<0$, the same argument works downward using levels $-d,-2d,\ldots,S$, so

$$f(a)\ge \tau(|S|).$$

If $S=0$, the full array is always a valid partition, so

$$f(a)\ge 1.$$

That is the lower bound. Now we need to hit it exactly, because otherwise we are just doing math cosplay.

Construction With No Extra Junk

Take the brutally simple array:

$$a=[\underbrace{1,1,\ldots,1}_{x\text{ times}},\underbrace{-1,-1,\ldots,-1}_{y\text{ times}}].$$

If $S>0$, then $x>y$, and the prefix sums look like

$$0,1,2,\ldots,x,x-1,x-2,\ldots,S.$$

For a divisor $d\mid S$, the internal cut levels are

$$d,2d,\ldots,S-d.$$

All of these are strictly less than $S$, and each of them appears exactly once in this prefix walk. The final level $S$ is handled by the end of the array. So for this $d$, there is exactly one partition.

No other block sum can appear, because any valid block sum $q$ must satisfy $kq=S$. Thus the construction has exactly $\tau(S)$ valid partitions.

For $S<0$, the same construction works symmetrically: the required negative prefix levels are each hit exactly once while the walk descends.

For $S=0$, the prefix sums are

$$0,1,2,\ldots,x,x-1,\ldots,0.$$

The value $0$ appears only at the start and the end. Since every valid partition must have block sum $0$, there is no internal place to cut. Only the whole array works, so $f(a)=1$.

Therefore the minimum is

$$\boxed{ \begin{cases} 1, & x=y,\\ \tau(|x-y|), & x\ne y. \end{cases}}$$

We output this value modulo $676\,767\,677$, and output the constructed array above.

Complexity

Counting divisors by trial division costs

$$O(\sqrt{|x-y|})$$

per test case, and printing the array costs $O(x+y)$. Since $|x-y|\le 2\cdot 10^5$, this is easily fast enough.

Overall:

$$O\left(t\sqrt{2\cdot 10^5}+\sum (x+y)\right)$$

time and $O(1)$ extra memory.

Reference checked: official Codeforces editorial.