One possible issue in your problem is you don't check any of the initial queries for if they are equal to 'CENTER'
On Wed, 22 Apr 2020, 16:32 Arti Schmidt, <artischmi...@gmail.com> wrote: > In Round 1B 2020 I'm getting TLE on test set 3 for Blindfolded Bullseye > using nearly the same strategy explained in the analysis (binary search > from a point in the dartboard to the edge of the wall in four directions > and find midpoints). The only difference is how I am finding the initial > point inside the dartboard. I queried points (-10^9/2, 0), (10^9/2, 0), (0, > -10^9/2), and (0, 10^9/2). I thought this would ensure that at least one > point is in the dartboard, but I must be missing something because when I > add a few additional points to query my program passes all test sets. My > full program is below, can anyone tell me why it doesn't work with just the > four mentioned points? > > bound_max = 10 ** 9 > t, a, b = map(int, input().split()) > > def query(x, y): > print(x, y) > return input() > > def binary_search(lower, upper, axis, pos, miss_lower): > while lower < upper: > mid = (lower + upper) // 2 > point = (mid, pos) if axis == 'x' else (pos, mid) > if query(*point) == 'MISS': > if miss_lower: > lower = mid + 1 > else: > upper = mid - 1 > else: > if miss_lower: > upper = mid - 1 > else: > lower = mid + 1 > return upper if upper > -bound_max else -bound_max > > for case in range(t): > > # fails with these points > points = ( > (-bound_max // 2, 0), > (bound_max // 2, 0), > (0, -bound_max // 2), > (0, bound_max // 2) > ) > > # succeeds with these points > points = ( > (-bound_max // 2, -bound_max // 2), > (0, -bound_max // 2), > (bound_max // 2, -bound_max // 2), > (-bound_max // 2, 0), > (0, 0), > (bound_max // 2, 0), > (-bound_max // 2, bound_max // 2), > (0, bound_max // 2), > (bound_max // 2, bound_max // 2), > ) > > for point in points: > if query(*point) == 'HIT': > hit_x, hit_y = point > break > > left = binary_search(-bound_max, hit_x, 'x', hit_y, True) > right = binary_search(hit_x, bound_max, 'x', hit_y, False) > bot = binary_search(-bound_max, hit_y, 'y', hit_x, True) > top = binary_search(hit_y, bound_max, 'y', hit_x, False) > > x = (left + right) // 2 > y = (bot + top) // 2 > > done = False > for i in range(-2, 3): > for j in range(-2, 3): > if query(x + i, y + j) == 'CENTER': > done = True > break > if done: > break > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to google-code+unsubscr...@googlegroups.com. > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/3cba1a61-2b8b-4925-ade2-2534fb88dc3f%40googlegroups.com > <https://groups.google.com/d/msgid/google-code/3cba1a61-2b8b-4925-ade2-2534fb88dc3f%40googlegroups.com?utm_medium=email&utm_source=footer> > . > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to google-code+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CAECKw-NnefCPqLPh24NoniJVJ_tafZ6XcqRtgoTgj-zq-t3YzA%40mail.gmail.com.
