I have seen people use binary search in this particular problem 1443C - The Delivery Dilemma but my submission is getting TLE in testcase 9 166040767 Can anyone explain why is that? for example this binary search solution passed 97454890
I have seen people use binary search in this particular problem 1443C - The Delivery Dilemma but my submission is getting TLE in testcase 9 166040767 Can anyone explain why is that? for example this binary search solution passed 97454890
Here is your corrected submision. Reason for TLE is passing the whole vector to function (in brief: every time you pass vector to function, you make his copy, and it's ineffective) instead of passing only his reference.
that's not entirely true. it takes O(n) to copy a vector, and the binary search runs in O(log(1e9)), which is essentially O(32*n) which should pass. See their testcase 8. There's something else that's wrong in their code.
But it passed when I passed the reference of the vectors.
That is an O(n) speedup, which is nevertheless a lot, and definitely enough to compensate for other problems. There is something else that is wrong here, not the vector copy (I've made plenty of Binary Searches which copy vectors).