CF721D Maxim and Array

最近 Maxim 发现了一个由 $n$ 个整数组成的数组，这些数无人需要。他立刻萌生了改变这个数组的想法：他发明了一个正整数 $x$，并决定对数组中的任意元素加上或减去 $x$。具体来说，每次操作，Maxim 选择一个整数 $i$（$1 \leq i \leq n$），并将第 $i$ 个数组元素 $a_i$ 替换为 $a_i + x$ 或 $a_i - x$。请注意，同一位置可以进行多次操作。 Maxim 是个好奇又极简主义的人，因此他想知道，在对数组最多进行 $k$ 次操作后，所有数组元素的乘积（即 $\prod_{i=1}^{n} b_i$）可能达到的最小值是多少？请帮帮他。

输入的第一行包含三个整数 $n$、$k$ 和 $x$（$1 \leq n, k \leq 200000, 1 \leq x \leq 10^9$）——数组的元素个数、最多允许操作的次数以及 Maxim 想出的数。 第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$|a_i| \leq 10^9$）——Maxim 找到的数组元素。

输出 $n$ 个整数 $b_1, b_2, ..., b_n$，即在对数组最多进行了 $k$ 次操作后得到的数组元素。特别地，对每个 $1 \leq i \leq n$，应有 $b_i = a_i + m_i \times x$，其中 $m_i$ 为某个整数，并且所有 $|m_1| + |m_2| + ... + |m_n| \leq k$，使得所有数组元素的乘积最小。 如果存在多组答案，输出其中任意一组即可。

由 ChatGPT 5 翻译