P12543 [APIO2025] Rotating Lines

Asadullo is an outstanding researcher at APIO (Alliance for Power and Industrial Optimization). Recently, he has been studying a method to generate energy using an unknown material. This unknown material does not produce energy on its own, but if there are several extremely long rods made of this material, they can generate energy through their interactions. Specifically, there are $n$ rods, given by an array $v[0], v[1], \ldots, v[n-1]$. The $i$-th rod can be positioned at an angle of $a[i] = 360 \cdot \frac{v[i]}{100000}$, with respect to the positive direction of the x-axis, in counterclockwise. The energy efficiency by these $n$ rods is defined as $$\sum_{i

N/A

N/A

### Examples #### Example 1 Consider the following call: ```cpp energy(2, [20000, 10000]) ``` Here, $v = [20000, 10000]$ and the initial energy efficiency equals $20000 - 10000 = 10000$. One of the possible scenarios is the following: - call `rotate([0, 1], 8000)`. Then $v$ becomes $[28000, 18000]$. The energy efficiency stays the same. - call `rotate([0], 15000)`. Then $v$ becomes $[43000, 18000]$. The energy efficiency becomes $43000 - 18000 = 25000$. It can be shown that for the given input, 25000 is the maximum possible energy efficiency. Therefore, Asadullo can stop performing these operations. #### Example 2 Consider the following call: ```cpp energy(3, [5000, 12500, 37500]) ``` The image for this example was presented above. It can be shown that the initial energy efficiency is the maximum possible. Thus, no operations are needed. ### Constraints - $2 \leq n \leq 100 \, 000$ - $0 \leq v[i] \leq 49 \, 999$ for each $0 \leq i < n$ - elements of $v$ are **not** necessarily distinct ### Subtasks 1. (5 points) $n = 2$ 2. (11 points) $v[i] < 25 \, 000$ for each $0 \leq i < n$ 3. (8 points) $n \leq 10$ 4. (15 points) $n \leq 100$ 5. (15 points) $n \leq 300$ 6. (20 points) $n \leq 2000$ 7. (26 points) No additional constraints. ### Sample Grader The sample grader reads the input in the following format: - line 1: $n$ - line 2: $v[0] \, v[1] \ldots \, v[n - 1]$ The sample grader prints the output in the following format: - line 1: final energy efficiency of rods Also, the grader will write detailed information about the rotations you made in the file `log.txt`.