Recently in the div 4 contest (Codeforces Round 964 (Div. 4)), I tried to hack some people's problem E solution, and I find some strange things.
In problem E, the solution should be like this :
1. for all x from 1 to 2e5, precompute the number of operations needed for x to become 0
2. construct a partial sum array to store those information
3. for each query, use O(1) time complexity to answer with partial sum
(you can refer to the editorial for more)
I AC the task with time 109ms with the solution described above.
However, after the contest, I found that there are many people passed this task without using partial sum, instead they just use O(n) time complexity for each query. The time used by these solutions are about 800ms-900ms, which didn't cause TLE.
But why? If we use a test case that all query is 1 200000
, the code will loop more than 1e4*2e5=2e9 times, which is not expected to pass, even with the pragma gcc optimize thing.
I have attempted to hack many of those solutions, but only one of it is successful hack.
submission
hack case
The above one is one of the submission that I got an unsuccessful hack. This solution passed the case in 827ms.
submission
The above one is one of the submission that I got an successful hack. (TLE)
Is that the compiler "helped" the author to make a fast range sum query automatically? If not why this happened?