P9654 "GROI-R2" Memory Fragments

Fragments of memory are scattered everywhere, and Alice wants to piece them back together. The order of the fragments is fixed, because memory obviously cannot proceed backward. However, the shape and content of each fragment can be polished and adjusted—after all, everyone’s memories get distorted and forgotten. The memory on each fragment can be represented by a **non-negative integer**. Two adjacent fragments can be perfectly joined if and only if the sum of their memories is a **perfect square**. Now Alice can polish some fragments so that every pair of adjacent fragments can be perfectly joined. In each polishing operation, Alice may choose one fragment and change the memory on it to any **non-negative integer**. Alice wants to know the minimum number of fragments she must polish to achieve her goal. She also wants you to output what memory remains on each fragment after polishing. **Formal statement** Given a **non-negative integer** sequence $\{a_n\}$, we define one operation as choosing any $i\in [1,n]$ and changing $a_i$ to any **non-negative integer** $x$. Ask for the minimum number of operations needed so that $\forall i\in [1,n-1]$, $a_i+a_{i+1}$ is a **perfect square**, and output a modification scheme.

The first line contains an integer $n$, the number of memory fragments. The second line contains a non-negative integer sequence $a$ of length $n$, representing the memory on each fragment.

The first line outputs an integer, the minimum number of polishing operations. The second line outputs an integer sequence of length $n$, representing the memory on every fragment after all polishing. You must ensure that the memories after polishing satisfy the conditions in the statement, match the minimum number of operations you output, and that each fragment’s memory lies in the range $[0,10^{18}]$.

**Sample explanation** For the first sample, it is not hard to prove that Alice must polish at least one fragment to make all memories satisfy the condition. Please note that the order of the memory fragments cannot be changed. **Scoring rules** If the minimum number of polishing operations you output is correct for a test point, you will get $30\%$ of the score for that test point. If, based on the correct minimum number, you also provide a correct construction, you will get $100\%$ of the score for that test point. If you can only compute the minimum number of operations, please still output $n$ integers separated by spaces on the second line, each within $[0,10^{18}]$, otherwise you may receive $0$ points. Please note that in each subtask, the $30\%$ score you get will be floored. **Constraints** **This problem uses bundled tests**. | $\text{Subtask}$ | $n\le$ | $a_i\le$ | Special property | Score | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $2$ | $10^8$ | | $5$ | | $2$ | $3$ | $10^8$ | | $20$ | | $3$ | $4$ | $10^8$ | | $15$ | | $4$ | $10^3$ | $10^8$ | | $15$ | | $5$ | $10^6$ | $10^4$ | | $10$ | | $6$ | $10^6$ | $10^8$ | $\text{A}$ | $10$ | | $7$ | $10^6$ | $10^8$ | | $25$ | Special property $\text{A}$: $\forall 1\le i,j\le n$, $a_i=a_j$. For $100\%$ of the testdata, $1\le n\le 10^6$ and $0\le a_i\le 10^8$. Translated by ChatGPT 5