Abstract↵
------------------↵
↵
1. Never apply a binary search on `std::list`.↵
2. If you want to make a custom `_Comp` function for `std::set` , write down as many instructions to distinguish elements in the set as possible.↵
↵
[cut] I think it's important.↵
↵
Detail↵
------------------↵
↵
When I was solving one of the problems in the ConstructorU's Open Cup's Practice Round, I wrote this ↵
↵
~~~~~↵
lst.insert(lower_bound(lst.begin(),lst.end(),idx,[&](int a,int b){↵
return x[p[a]]<x[p[b]];↵
}),idx);↵
~~~~~↵
↵
when `lst` is a `std::list` . I will insert a permutation with a size about $2\times 10^5$ in it.↵
↵
But after I waited for a half minute, I killed the process.↵
↵
So I took a look in the file `stl_algobase.h` , then deep in the file `stl_iterator_base_funcs.h` , I found the function `__advance` which drives `lower_bound` and other binary-search functions designed for containers with bidirectional iterators:↵
↵
~~~~~↵
template<typename _BidirectionalIterator, typename _Distance>↵
inline _GLIBCXX14_CONSTEXPR void↵
__advance(_BidirectionalIterator& __i, _Distance __n,↵
bidirectional_iterator_tag)↵
{↵
// concept requirements↵
__glibcxx_function_requires(_BidirectionalIteratorConcept<↵
_BidirectionalIterator>)↵
if (__n > 0)↵
while (__n--)↵
++__i;↵
else↵
while (__n++)↵
--__i;↵
}↵
~~~~~↵
↵
I was shocked because its time complexity is $O(n)$ .↵
↵
Considered that `vector` may solve this problem but have a higher time complexity when massively insert elements in the front of it, I used `set` instead, and modified the lambda function I wrote above to the `_Comp` function of it.↵
↵
It passed the sample, but it got a Wrong verdict.↵
↵
When I tried to debug, I was confused when I saw that the `set` said $4=5$ . Then, I found that $x[p[4]]=x[p[5]]$ in my input.↵
↵
So I modified the function `_Comp` a bit to this:↵
↵
~~~~~↵
lst.insert(lower_bound(lst.begin(),lst.end(),idx,[&](int a,int b){↵
if(x[p[a]]^x[p[b]])return x[p[a]]<x[p[b]];↵
return a<b;↵
}),idx);↵
~~~~~↵
↵
Then, it passed the test.↵
↵
Thanks [user:ConstructorU,2024-02-03], you taught me a great lesson.↵
↵
↵
↵
↵
↵
↵
↵
------------------↵
↵
1. Never apply a binary search on `std::list`.↵
2. If you want to make a custom `_Comp` function for `std::set` , write down as many instructions to distinguish elements in the set as possible.↵
↵
[cut] I think it's important.↵
↵
Detail↵
------------------↵
↵
When I was solving one of the problems in the ConstructorU's Open Cup's Practice Round, I wrote this ↵
↵
~~~~~↵
lst.insert(lower_bound(lst.begin(),lst.end(),idx,[&](int a,int b){↵
return x[p[a]]<x[p[b]];↵
}),idx);↵
~~~~~↵
↵
when `lst` is a `std::list` . I will insert a permutation with a size about $2\times 10^5$ in it.↵
↵
But after I waited for a half minute, I killed the process.↵
↵
So I took a look in the file `stl_algobase.h` , then deep in the file `stl_iterator_base_funcs.h` , I found the function `__advance` which drives `lower_bound` and other binary-search functions designed for containers with bidirectional iterators:↵
↵
~~~~~↵
template<typename _BidirectionalIterator, typename _Distance>↵
inline _GLIBCXX14_CONSTEXPR void↵
__advance(_BidirectionalIterator& __i, _Distance __n,↵
bidirectional_iterator_tag)↵
{↵
// concept requirements↵
__glibcxx_function_requires(_BidirectionalIteratorConcept<↵
_BidirectionalIterator>)↵
if (__n > 0)↵
while (__n--)↵
++__i;↵
else↵
while (__n++)↵
--__i;↵
}↵
~~~~~↵
↵
I was shocked because its time complexity is $O(n)$ .↵
↵
Considered that `vector` may solve this problem but have a higher time complexity when massively insert elements in the front of it, I used `set` instead, and modified the lambda function I wrote above to the `_Comp` function of it.↵
↵
It passed the sample, but it got a Wrong verdict.↵
↵
When I tried to debug, I was confused when I saw that the `set` said $4=5$ . Then, I found that $x[p[4]]=x[p[5]]$ in my input.↵
↵
So I modified the function `_Comp` a bit to this:↵
↵
~~~~~↵
lst.insert(lower_bound(lst.begin(),lst.end(),idx,[&](int a,int b){↵
if(x[p[a]]^x[p[b]])return x[p[a]]<x[p[b]];↵
return a<b;↵
}),idx);↵
~~~~~↵
↵
Then, it passed the test.↵
↵
Thanks [user:ConstructorU,2024-02-03], you taught me a great lesson.↵
↵
↵
↵
↵
↵
↵
↵
