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

Автор i_am_pikachu, история, 9 месяцев назад, По-английски

Code 1:

sort(all(edges), [&] (pair<int, int>& a, pair<int, int>& b) {
    return ((val[a.first]+val[a.second]) <= (val[b.first]+val[b.second]));
});

Code 2:

sort(all(edges), [&] (pair<int, int>& a, pair<int, int>& b) {
    return ((val[a.first]+val[a.second]) < (val[b.first]+val[b.second]));
});

These were a part of my solution to 2176D - Fibonacci Paths. The first code gave me runtime error on test case 8 but the later one is AC.

std::sort requires strict weak ordering, which means when comparing two equal objects the custom comparison function must return false. The reason for this being, under the hood std::sort uses < operator by default to compare two objects when no custom comparison function is given, hence when we do provide a custom function std::sort expects it to behave similar to the < operator. Using <= violates this expectation.

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

»
9 месяцев назад, скрыть # |
 
Проголосовать: нравится +13 Проголосовать: не нравится

Because when you use std::sort you need to ensure there's no pair of element satisfy cmp(a, b) && cmp(b, a).

»
9 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Because according to std::sort introsort implementation the final conclusion about comparator function is that: If cmp(a, b) is true then cmp(b, a) must be false. But reverse rule is not necessary, means if cmp(a, b) is false then cmp(b, a) does not have to be always true it can be false also. In-short cmp(a, b) and cmp(b, a) can't be both true, at least one of them has to be false.