Блог пользователя gourav_27

Автор gourav_27, история, 8 месяцев назад, По-английски

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??

  • Проголосовать: нравится
  • +13
  • Проголосовать: не нравится

»
8 месяцев назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

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

»
8 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

ya cauze 20 is not complete i think

»
8 месяцев назад, скрыть # |
 
Проголосовать: нравится +18 Проголосовать: не нравится

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.

»
8 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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