Editorial : Course Wishes

This editorial follows the greedy construction in model_sol.cpp.

Increasing a course’s wish level by $1$ moves one unit of “occupancy” from some level $\le k$ toward level $k{+}1$. The level $k{+}1$ is uncapped, so the only difficulty is not to violate the caps $a_1,\ldots,a_k$ on the way.

Process courses in non-increasing order of the current level $b_i$. Equivalently, first finish courses that are already closest to the target $k{+}1$, then work downward. This order ensures that whenever we still need to push a course upward from a small $b_i$, the cheaper levels have already been cleared as much as possible by earlier moves, so the caps remain feasible.

For each test case:

1. Read $n$, $k$, the caps $a_1,\ldots,a_k$, and the levels $b_1,\ldots,b_n$.
2. Build pairs $(b_i, i)$ and sort by descending $b_i$.
3. For each pair in that order, repeat: while $b_i \le k$, record an operation on index $i$ and increment $b_i$.
4. Output the total number of recorded operations and the list.

Under the constraints, the number of operations is at most $n \cdot k \le 1000$.

Compare any valid sequence with the greedy one in the same total multiset of “+1” moves per course. The greedy order maximizes how much mass has already been shifted into level $k{+}1$ before we still need to touch a course at a low level; this is exactly the ordering that avoids getting stuck under upper-level caps when a solution exists.

Sorting costs $O(n \log n)$ per test case; the simulation is $O(n k)$ operations, which is tiny under the given caps.