Editorial for Love Evenness

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: WilliamWu277

The strategy for this game is to arrange the largest \lfloor \frac{N}{2} \rfloor integers into the odd indices. When the demon king takes a number from an even index, it gets one of the smallest \lfloor \frac{N}{2} \rfloor integers, and all the integers above automatically switch parities. To reverse this parity switch, we take the index under the one that the demon king takes, getting one of the largest \lfloor \frac{N}{2} \rfloor integers and switching all the integers above back into the parities they started with. We simply repeat this until all the integers are gone. In the end, we can always end up with the largest \lfloor \frac{N}{2} \rfloor integers in our collection, leaving the smallest \lfloor \frac{N}{2} \rfloor integers for the demon king.

Time Complexity: \mathcal{O}(N \log N)


There are no comments at the moment.