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 [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/3cba1a61-2b8b-4925-ade2-2534fb88dc3f%40googlegroups.com.
