search

NachiaVivias / cp-library

https://nachiavivias.github.io/cp-library/
Creative Commons Zero v1.0 Universal
10 stars 0 forks source link

有理数二分探索 RationalNumberSearch の効率が悪い #13

Closed NachiaVivias closed 2 months ago

NachiaVivias commented 4 months ago

同じ有理数を 2 回以上質問する場合があります。

3 -> 0 , 4 -> 0 の遷移の間違いが原因です。

https://github.com/NachiaVivias/cp-library/blob/4d814fc3c2ed6555719399d9a5be7e41add1cff5/Cpp/Include/nachia/math/rational-number-search.hpp#L74-L86

NachiaVivias commented 2 months ago

修正の参考： https://judge.yosupo.jp/submission/197971