yshen94's blog

performance difference bewteen array and vector
By yshen94, 2 weeks ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Your cmp function is broken. The comparator should return false on elements that you consider equivalent: it should be return x.x+x.y < y.x+y.y;.

That is probably part of the reason for the runtime error, not some minute performance difference.

→ Reply
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are right, appreciate your explanation. but why cannot I have an equivalent sign?

    → Reply
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      C++ comparator should define the < sign. Using this, we automatically get the other two cases: x > y = !(x < y) and x == y = !(x < y) && !(x > y)

      → Reply
      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        the comparator issue only applies to vectors right?. in #287237470, it passes with a <=

        → Reply
        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          no, both causes undefined behavior, you just got lucky on the submission with array.

          → Reply
        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
          ← Rev. 3   Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    2 weeks ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    why were the first 3 testcases passed successfully?

    → Reply
    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Might be because equality comparison in never used in these tc

      → Reply
      • »
        »
        »
        »
        2 weeks ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        there might be other reasons, because if I test 1 2 2 1 it passes

        → Reply