Submission #857190

#TimeUsernameProblemLanguageResultExecution timeMemory
857190ollelWorm Worries (BOI18_worm)Pypy 3
59 / 100
1000 ms46692 KiB
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
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...