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

MLE while using comparator
Автор jac_nikola, история, 3 года назад, По-английски

PROBLEM LINK

MY CODE LINK

I'm getting MLE on submitting this solution. I suspect it has to do something with the comparators that I've used. I found some relevant information here.

Please help me figure out where exactly it's getting wrong. Thank you.

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

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

Auto comment: topic has been updated by jac_nikola (previous revision, new revision, compare).

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

If two elements are equal the comparator should always return 0.

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

    And yeah this. https://mirror.codeforces.com/blog/entry/70237

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

    I tried doing that but it's giving me incorrect result on the sample, whereas my previous comparator logic was working fine. Could you please tell how the comparator should look like according to you?

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

      You can refer to my submission

      https://mirror.codeforces.com/contest/1551/submission/123565021

      Here check the test function, pardon me for a messy template.

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

      The problem is whenever the if statement's condition evaluates to false, the return value is independent of the order of a and b, i. e. cmp(a, b) == cmp(b, a). Consider for instance the strings "aab" and "ab". cmp1 will always return 1, violating the asymmetry property of comparators. This is UB and can lead to all sorts of internal error in the library.

      → Ответить