oj.uz

Submission #857190

# Submission time Handle Problem Language Result Execution time Memory
857190 2023-10-05T14:12:21 Z ollel Worm Worries (BOI18_worm) PyPy 3
59 / 100
 1000 ms 46692 KB 
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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 29176 KB Output is correct
2 Correct 221 ms 29460 KB Output is correct
3 Correct 217 ms 28812 KB Output is correct
4 Correct 235 ms 29076 KB Output is correct
5 Correct 213 ms 29144 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 24324 KB invalid format (must have DIMS+1 tokens). input:
2 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 28024 KB Output is correct
2 Correct 160 ms 27784 KB Output is correct
3 Correct 160 ms 28036 KB Output is correct
4 Correct 161 ms 28128 KB Output is correct
5 Correct 178 ms 27816 KB Output is correct
6 Correct 163 ms 28152 KB Output is correct
7 Correct 161 ms 27544 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 28088 KB Output is correct
2 Correct 168 ms 28180 KB Output is correct
3 Correct 165 ms 27964 KB Output is correct
4 Incorrect 225 ms 29080 KB not a local maximum
5 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 551 ms 36580 KB Output is correct
2 Correct 565 ms 36216 KB Output is correct
3 Correct 569 ms 35944 KB Output is correct
4 Correct 557 ms 36020 KB Output is correct
5 Correct 603 ms 36836 KB Output is correct
6 Correct 580 ms 36652 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 672 ms 40916 KB Output is correct
2 Correct 679 ms 41484 KB Output is correct
3 Correct 690 ms 40392 KB Output is correct
4 Correct 843 ms 42492 KB Output is correct
5 Correct 828 ms 41996 KB Output is correct
6 Correct 770 ms 41896 KB Output is correct
7 Correct 834 ms 41880 KB Output is correct
8 Correct 961 ms 46692 KB Output is correct
9 Correct 983 ms 44824 KB Output is correct
10 Correct 1000 ms 46052 KB Output is correct
11 Correct 923 ms 45820 KB Output is correct