Represent the eating order as a permutation of the 100 cells. If other apples within distance 2 of cell were eaten earlier, eating yields points. The objective is therefore .
Simulated annealing can start from a random permutation. Propose swaps or insertion moves that relocate one apple and shift the intervening segment. Accept improvements; accept a decrease of with probability at temperature . Gradually lower the temperature, use multiple restarts, and preserve the best order seen separately from the current state.
Each cell has at most 12 other cells within distance 2. With neighbor lists and position arrays, update only the counts affected by changed relative orders to compute score differences quickly. Updating the position array after a move takes at most . Even a complete evaluation takes only .
Annealing does not guarantee reaching the AC threshold. Since the grid is fixed, it is also valid to search offline and store a chosen order in the submitted program. The reference solution prints an order found using swaps and insertions. Its exact score is , above the -point threshold, so it receives AC and retains the excess points. This is not a claim of global optimality. The reference program runs in time proportional to its output and performs no online search.
The naive solution visits cells in row order. It prints a valid permutation but earns a lower score.
The judge can compute the total exactly with integers. Since , multiplying scores by makes each contribution the integer . Return the uncapped total divided by as the checker multiplier. Because the subtask is worth points, the final judge score equals the actual total, up to the platform's display precision, even when the multiplier exceeds . A final score of at least is AC. Each term is at most and the total at most , safely within signed 64-bit integers.
Solution written by GPT6