NeutralMilkHotel's blog

Runtime Error while using comparator?
By NeutralMilkHotel, history, 4 years ago, In English

https://codeforces.net/contest/1148/submission/88665764 .Runtime error in https://codeforces.net/contest/1148/problem/D . I cannot figure out why there is runtime error, inspite of such low memeory being used. All the values are distinct in the problem.

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

Comments Comments (1)
| Write comment?
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

A C++ comparator must be a strict weak ordering. The three properties of a strict weak ordering is asymmetry, irreflexivity, and transitivity.

Asymmetry means that if $$$a < b$$$, then $$$b \not<a$$$.

Irreflexivity means $$$a<a$$$ is false.

Transitivity means if $$$a<b$$$ and $$$b<c$$$ then $$$a<c$$$.

Your comparator contradicts all three.

→ Reply