Hello, Codeforces!
I am solving this problem https://codeforces.me/contest/1665/problem/B
But I'm getting TLE on test case 13. I don't think there should be any TLE. Please look at my code and guide me what's wrong with my thought process. https://pastebin.com/EmhQpghv
I also optimized my code to get rid of inner while loop https://pastebin.com/5800fc8C But still get TLE on testcase 13.
Thanks for any help or suggestion!
endl is slow when you print lot of lines, use "\n" instead.
Here is an accepted submission.161839419
Thanks a lot for the help But I copied you code and getting TLE still https://codeforces.me/contest/1665/submission/161854064
Submit in C++20 (64) language, not C++17
I don't know why this behavior but it got accepted thanks
The problem is that you're using an unordered_map. The expected access time is in
O(1)
but in the worst case, when a lot of hash collisons occur it isO(n)
. This leads to your solution having a time complexity ofO(n^2)
which ist too slow. It seems to work with C++20 because it uses a different hash function and there is no designed testcase for this hash function. Your solution should be accepted if you use map instead of unordered_map.