P16917 [JLCPC 2026] Problem Sequence 1

You are given an integer sequence $a$ of length $n$, where each value is in $[0,2]$. One operation is defined as follows: - Choose an index $x$ ($1 \le x \le n - 2$). - Let $s=(a_x+a_{x+1}+a_{x+2}) \bmod 3$, then change $a_x, a_{x+1}, a_{x+2}$ all to $s$ at the same time. You need to perform several operations (possibly none) to maximize the sum of all numbers in the sequence $a$. At the same time, you must provide a valid operation plan whose number of operations does not exceed $\left\lfloor\dfrac{5}{7}n\right\rfloor+100$. It can be proven that a plan satisfying the operation limit always exists.

The first line contains an integer $T$ ($1 \le T \le 1000$), the number of test cases. Then follow $T$ blocks, each describing one test case: - The first line contains an integer $n$ ($3 \le n \le 10^6$), the length of the sequence $a$. - The second line contains $n$ integers; the $i$-th integer is $a_i$ ($0 \le a_i \le 2$). The data guarantees that $\sum n \le 10^6$.

For each test case: - The first line outputs two integers $s$ and $K$, representing the maximum possible sequence sum and the number of operations in your plan. You must ensure $0 \le K \le \left\lfloor\dfrac{5}{7}n\right\rfloor + 100$. - The next line outputs $K$ positive integers; the $i$-th integer is the chosen $x$ for the $i$-th operation.

Translated by ChatGPT 5