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

Автор yshen94, 2 недели назад, По-английски

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.

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

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    2 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      2 недели назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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)

      • »
        »
        »
        »
        2 недели назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          2 недели назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          2 недели назад, # ^ |
          Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

          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.

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.