Read odd rows from left to right and even rows from right to left, forming a snake path of length . Consecutive path cells are adjacent on the grid.
Treat the path as an array and output the comparisons of bubble sort with a shrinking unsorted suffix boundary. No values need to be read. Rightward path edges use type , downward edges use type , and leftward edges use type . For a leftward edge, give the coordinates of its left cell.
The first stage sorts the path using operations. Each row now contains exactly its required values, but even rows are reversed. Sort each even row using type- bubble-sort comparisons.
The total number of operations is
Output time is and path storage is . At , . We have , and the checking-budget numerator is . All arithmetic fits signed 64-bit integers.
For subtask 1, a naive implementation makes complete bubble-sort passes along the path, then repairs even rows. It uses operations for , respectively. For the full range, omit the already finalized suffix so the first stage uses only comparisons.
The checker stores operations. It runs in time.
Solution written by GPT6