Submission #857190

#	Time	Username	Problem	Language	Result	Execution time	Memory
857190		ollel	Worm Worries (BOI18_worm)	Pypy 3	59 / 100	1000 ms	46692 KiB

worm

from random import randint

queries_made = 0
n, m, k, q = [int(i) for i in input().split()]

cache = {}

def ask(t):
    global queries_made
    x, y, z = t
    if x < 1 or x > n or y < 1 or y > m or z < 1 or z > k or queries_made == q:
        return -1
    if (x, y, z) in cache:
        return cache[(x, y, z)]
    
    queries_made += 1
    print(f"? {x} {y} {z}")
    ans = int(input())
    cache[(x, y, z)] = ans
    return ans

def answer(t):
    x, y, z = t
    print(f"! {x} {y} {z}")
    exit(0);

def biggest_neighbor(t):
    x, y, z = t
    ans = (x, y, z)
    r = ask(ans)
    
    neis = [(x+1,y,z),(x-1,y,z),(x,y+1,z),(x,y-1,z),(x,y,z+1),(x,y,z-1)]
    for nei in neis:
        r2 = ask(nei)
        if r2 > r:
            r = r2
            ans = nei
    
    return ans

def get_rand():
    return (randint(1,n), randint(1,m), randint(1,k))

R = q//3
W = q-R

start = None
score = 0
for i in range(R):
    test = get_rand()
    ts = ask(test)
    if ts > score:
        start = test
        score = ts
    
while queries_made < q:
    b = biggest_neighbor(start)
    if b == start:
        answer(b)
    start = b

• Subtask 1: 10 / 10
• Subtask 2: 0 / 22
• Subtask 3: 12 / 12
• Subtask 4: 0 / 19
• Subtask 5: 14 / 14
• Subtask 6: 23 / 23