NeutralMilkHotel's blog

By NeutralMilkHotel, history, 6 years ago, In English

https://mirror.codeforces.com/contest/1148/submission/88665764 .Runtime error in https://mirror.codeforces.com/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.

| Write comment?
»
6 years ago, hide # |
 
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 \lt b$$$, then $$$b \not \lt a$$$.

Irreflexivity means $$$a \lt a$$$ is false.

Transitivity means if $$$a \lt b$$$ and $$$b \lt c$$$ then $$$a \lt c$$$.

Your comparator contradicts all three.