can anyone tell me the reason of RTE in the following submission :-
https://www.codechef.com/viewsolution/25954983
for problem :-
https://www.codechef.com/problems/ONEKING
can anyone tell me the reason of RTE in the following submission :-
https://www.codechef.com/viewsolution/25954983
for problem :-
https://www.codechef.com/problems/ONEKING
One immediate problem that might be causing internal errors during the call to sort
is that your ordering operator is wrong:
a.f <= b.f
should be
a.f < b.f
There might be other errors, but that’s the one I spotted first
Edit:
Just tried locally with
g++ -std=c++14 aarls-one-kingdom.cpp -g3 -O3
and randomly-generated testcases, and it crashed pretty quickly:
std::__unguarded_partition<std::pair<long long, long long>*, __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(std::pair<long long, long long>, std::pair<long long, long long>)> > (__comp=...,
__pivot=<optimised out>, __last=0x7fffffedeff0, __first=0x7fffffeef280) at /usr/include/c++/7/bits/stl_algo.h:1905
1905 while (__comp(__pivot, __last))
(gdb) bt
#0 std::__unguarded_partition<std::pair<long long, long long>*, __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(std::pair<long long, long long>, std::pair<long long, long long>)> > (__comp=...,
__pivot=<optimised out>, __last=0x7fffffedeff0, __first=0x7fffffeef280) at /usr/include/c++/7/bits/stl_algo.h:1905
#1 std::__unguarded_partition_pivot<std::pair<long long, long long>*, __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(std::pair<long long, long long>, std::pair<long long, long long>)> > (__comp=...,
__last=0x7fffffeeffa0, __first=0x7fffffeef240) at /usr/include/c++/7/bits/stl_algo.h:1923
#2 std::__introsort_loop<std::pair<long long, long long>*, long, __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(std::pair<long long, long long>, std::pair<long long, long long>)> > (
__first=__first@entry=0x7fffffeef240, __last=0x7fffffeeffa0, __last@entry=0x7fffffffdb50, __depth_limit=26, __depth_limit@entry=32, __comp=..., __comp@entry=...)
at /usr/include/c++/7/bits/stl_algo.h:1952
#3 0x0000000000400adb in std::__sort<std::pair<long long, long long>*, __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(std::pair<long long, long long>, std::pair<long long, long long>)> > (
__comp=..., __last=0x7fffffffdb50, __first=0x7fffffeef240) at /usr/include/c++/7/bits/stl_algo.h:1968
#4 std::sort<std::pair<long long, long long>*, bool (*)(std::pair<long long, long long>, std::pair<long long, long long>)> (
__comp=0x400ff0 <cmp(std::pair<long long, long long>, std::pair<long long, long long>)>, __last=0x7fffffffdb50, __first=0x7fffffeef240) at /usr/include/c++/7/bits/stl_algo.h:4868
#5 main (argc=<optimised out>, argv=<optimised out>) at aarls-one-kingdom.cpp:75
Using
g++ -std=c++14 aarls-one-kingdom.cpp -g3 -O3 -D_GLIBCXX_DEBUG
of course, finds it immediately:
/usr/include/c++/7/bits/stl_algo.h:4866:
Error: comparison doesn't meet irreflexive requirements, assert(!(a < a)).
Re-running with the suggested fix reveals no further crashes, so far.
hey thanks buddy, it worked
but i am little confused as it should work fine, but didn’t know why its showing such a behaviour
and can you tell me how you debugged it?
The comparison operator provided to sort
must give a “strict weak ordering”, else the behaviour is Undefined.
To be honest, I myself am slightly surprised that it could lead to a crash instead of “just” a wrong answer!
I debugged it just by bombarding your program with random testcases until one caused a segfault, then used gdb
to get a backtrace for the crash.