gourav_27's blog

Solution "Accepted" in C++17 and "TLE" in C++20 !?!
By gourav_27, history, 8 months ago, In English

This problem 2061D - Kevin and Numbers, i just solved today.

initially i was getting a TLE 335481507 in C++20,

but when i switched to C++17 ans pasted the exact same code 335481556 ,it got Accepted !!

Can anyone tell why is this happening??

  • Vote: I like it
  • +13
  • Vote: I do not like it

»
8 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

I think this has to do with the fact CodeForces C++20 is 64-bit and uses 64-bit memory addresses and C++17 32-bit. There are other blogs about this

→ Reply
»
8 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

ya cauze 20 is not complete i think

→ Reply
»
8 months ago, hide # |
 
Vote: I like it +18 Vote: I do not like it

The reason for the TLE is that the time complexity of con.count(x) is $$$O(\log(con.size()) + con.count(x))$$$ (see std::multiset::count).
So, your code is $$$O(n \times m)$$$.

It did not TLE in [GCC 7.3.0 32-bit C++17] because that version of GCC recognizes expressions of the form con.count(x) > 0 and optimizes them to con.find(x) != con.end() which are only $$$O(\log(con.size()))$$$. Of course, such optimizations are inconsistent and one should always do the conversion manually.

Regarding some other comments: This has nothing to do with the bitness of the architecture. The memory usage displayed for the C++20 submission is actually less then the C++17 submission (since it TLE'd before allocating more memory). Also, the incomplete support for C++20 will not make a difference in CP since the only incomplete C++20 feature in gcc is modules.

→ Reply
»
8 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Same code TLEs in C++20 (g++11.2) but passes in C++17 (g++9.2) due to slower stdlib/I-O constants

→ Reply