In the BREAK problem of MARCH LONG CHALLENGE 2020 , the first sub task gave WA in one of its test cases if i did it using a set but gave AC when i used map instead of set with the same logic. Can anyone identify the problem in the implementation using set , as it gave WA only in a single test case.
Link of the problem:
My solution using set:
https://www.codechef.com/viewsolution/30403508
My solution using map:
https://www.codechef.com/viewsolution/30489122
There’s quite a few differences between the two, but this at line 40 in your WA version leaps out:
auto x=st.end();
if(*it==st.size() && arr[i]!=*x)
st.end() is a one-past-the-end iterator, and dereferencing it is Undefined Behaviour:
/usr/include/c++/7/debug/safe_iterator.h:270:
Error: attempt to dereference a past-the-end iterator.
Objects involved in the operation:
iterator "this" @ 0x0x7ffc418971d0 {
type = __gnu_debug::_Safe_iterator<std::_Rb_tree_const_iterator<int>, std::__debug::set<int, std::less<int>, std::allocator<int> > > (mutable iterator);
state = past-the-end;
references sequence with type 'std::__debug::set<int, std::less<int>, std::allocator<int> >' @ 0x0x7ffc41897290
}
Aborted (core dumped)
I think you can use st.rend() if I’m not mistaken
“st.rbegin()” - “st.rend()” is also not de-referenceable 
There are other bugs, though - it is de-referenced without checking if it is valid; etc.
but why does it fail on only one test case?