really curious about the performance difference bewteen array and vector.
for 2023A — Concatenation of Arrays,
I passed the test using array as in #287237470 while failed the test using vector as in #287234748. The error shows "exit code: -1073741819 (STATUS_ACCESS_VIOLATION), checker exit code: 0, verdict: RUNTIME_ERROR"
maybe I am quite new in Codeforces. will be digging deeper into the performance difference.
Your
cmp
function is broken. The comparator should return false on elements that you consider equivalent: it should bereturn x.x+x.y < y.x+y.y;
.That is probably part of the reason for the runtime error, not some minute performance difference.
You are right, appreciate your explanation. but why cannot I have an equivalent sign?
C++ comparator should define the
<
sign. Using this, we automatically get the other two cases:x > y = !(x < y)
andx == y = !(x < y) && !(x > y)
the comparator issue only applies to vectors right?. in #287237470, it passes with a <=
no, both causes undefined behavior, you just got lucky on the submission with array.
Hacked. The C++ standard requires the comparator to follow strict weak ordering, and violating it is an undefined behavior. I don't exactly know what happens inside the
sort
function when it's violated, but it seems like it leads to accessing to an out of bound of the range you have given, and it doesn't always cause runtime error. I ran stress testing with your code and found some RT cases but they mostly failed to hack. Trying with almost the same test multiple times worked.I made the same mistake that my comparator returns true if elements are equivalent. After receiving a runtime error I passed the code for ChatGPT for debugging. It immediately pinpointed the bug.. Most of the time, AI tools help me debug really quickly.
why were the first 3 testcases passed successfully?
Might be because equality comparison in never used in these tc
there might be other reasons, because if I test 1 2 2 1 it passes