Today I was attempting to hack this submission for 2061B. In this solution, the code uses s1.count(x) inside the input-reading loop. Since the time complexity of multiset's count function is $$$O(\log n + k)$$$, where $$$k$$$ is the number of occurrences of the element, the code's time complexity should become $$$O(n^2)$$$ if all elements $$$a_i$$$ are set to $$$1$$$.
However, when I submitted the hack, this code only took 109 ms. Local testing showed that it indeed results in a TLE without -O2, but runs very quickly with -O2 enabled. Does this indicate that the compiler optimizes std::multiset.count() when it is used as boolean?








I think so.
Putting the code in compiler explorer, you can see the assembly generated when using
count()as boolean has one lessstd::_Rb_tree_increment(std::_Rb_tree_node_base const*)loop.Meanwhile the modified one that uses
count(a) == 10haswhich seems to be the process of
count()as it has acmp rbp, 10(comparing if the count == 10).lucky_clover_ Bedge
It was really, and I did a test.
When entering
1 1, the result of not turning onO2in this code is stuck, while when turned on, it ends quickly.Similarly, I think
O2has turnedif (s.count(y))intoif (s.find(y) != s.end()). This greatly improves the running speed of the program. Oh, I didn't knowO2was so powerful before.Finally, I am a middle school student. And if there are any errors, please feel free to point them out.
When I checked this myself, I noticed a very unusual behavior. I tried submitting the following two programs:
Code-1:
Code-2:
The only difference between 2 codes is I commented
cout<<x<<'\n;line. I checked both the programs on Codeforces and Codechef compilers.Runtime Comparison:
I seek to understand the reasons for this drastic increase in time complexity and runtime caused by this seemingly minor modification.
Because now you calculate something, but don't output any result. It means that compiler optimize it to:
int main() { return 0; }This optimization is inconsistent. This solution TLEs with C++20 but passes with C++23. Replacing count with contains lets it pass with C++20. I haven't been able to replicate this with a simpler program in custom invocation so I don't know why it works in C++23 but not C++20.