#include <bits/stdc++.h>
using namespace std;
int n, m, k, q;
map<tuple<int, int, int>, int> mym;
int ask(int a = 1, int b = 1, int c = 1){
if (a < 1 || b < 1 || c < 1 || a > n || b > m || c > k)
return 0;
if (mym.count(make_tuple(a, b, c)))
return mym[make_tuple(a, b, c)];
printf("? %d %d %d\n", a, b, c), fflush(stdout);
int ans;
scanf("%d", &ans);
if (ans == -1) exit(0);
return mym[make_tuple(a, b, c)] = ans;
}
void answer(int a = 1, int b = 1, int c = 1){
printf("! %d %d %d\n", a, b, c), fflush(stdout);
exit(0);
}
bool check(int a = 1, int b = 1, int c = 1){
if (max(ask(a-1, b, c), ask(a+1, b, c)) > ask(a, b, c))
return false;
if (max(ask(a, b-1, c), ask(a, b+1, c)) > ask(a, b, c))
return false;
if (max(ask(a, b, c-1), ask(a, b, c+1)) > ask(a, b, c))
return false;
return true;
}
void solve_1D(){
int l = 1, r = n, m1, m2, keep = 0;
while (l < r){
swap(m1, m2);
if (keep != 1)
m1 = ceil(0.62*l + 0.38*r);
if (keep != 2)
m2 = floor(0.38*l + 0.62*r);
if (m1 > m2)
swap(m1, m2);
if (m1 == m2)
(l < m1 ? m1-- : m2++);
assert(m1 < m2);
if (ask(m1) >= ask(m2))
r = m2-1, keep = 2;
else
l = m1+1, keep = 1;
}
answer(l);
}
void solve_2D(){
int l1 = 1, r1 = n, l2 = 1, r2 = m, x = 0, y = 0;
while (l1 < r1 || l2 < r2){
if (r1-l1 >= r2-l2){
int mid = (l1+r1)/2, a = mid, b = l2;
for (int i = l2; i <= r2; i++)
if (ask(mid, i) > ask(a, b))
a = mid, b = i;
if (ask(a, b) < ask(x, y))
(x > a ? l1 = mid+1 : r1 = mid-1);
else if (ask(a+1, b) > ask(a, b))
l1 = mid+1, x = a, y = b;
else if (ask(a-1, b) > ask(a, b))
r1 = mid-1, x = a, y = b;
else
answer(a, b);
}
else{
int mid = (l2+r2)/2, a = l1, b = mid;
for (int i = l1; i <= r1; i++)
if (ask(i, mid) > ask(a, b))
a = i, b = mid;
if (ask(a, b) < ask(x, y))
(y > mid ? l2 = mid+1 : r2 = mid-1);
else if (ask(a, b+1) > ask(a, b))
l2 = mid+1, x = a, y = b;
else if (ask(a, b-1) > ask(a, b))
r2 = mid-1, x = a, y = b;
else
answer(a, b);
}
}
answer(l1, l2);
}
void solve_3D(){
int tries = 50000, x = 0, y = 0, z = 0;
while (tries--){
int a = rand()%n+1, b = rand()%m+1, c = rand()%k+1;
if (ask(a, b, c) > ask(x, y, z))
x = a, y = b, z = c;
}
int da[] = {0, 0, 0, 0, 1, -1};
int db[] = {0, 0, 1, -1, 0, 0};
int dc[] = {1, -1, 0, 0, 0, 0};
while (true){
int a, b, c, local = 1;
for (int d = 0; d < 6; d++){
a = x+da[d];
b = y+db[d];
c = z+dc[d];
if (ask(a, b, c) > ask(x, y, z)){
local = 0;
break;
}
}
if (local)
answer(x, y, z);
x = a, y = b, z = c;
}
}
int main(){
scanf("%d %d %d %d", &n, &m, &k, &q);
if (k > 1)
solve_3D();
else if (m > 1)
solve_2D();
else
solve_1D();
return 0;
}
Compilation message
worm.cpp: In function 'int ask(int, int, int)':
worm.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
16 | scanf("%d", &ans);
| ~~~~~^~~~~~~~~~~~
worm.cpp: In function 'int main()':
worm.cpp:130:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
130 | scanf("%d %d %d %d", &n, &m, &k, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
256 KB |
Output is correct |
5 |
Correct |
1 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
256 KB |
Output is correct |
5 |
Correct |
1 ms |
256 KB |
Output is correct |
6 |
Correct |
1 ms |
256 KB |
Output is correct |
7 |
Correct |
1 ms |
256 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
256 KB |
Output is correct |
10 |
Correct |
1 ms |
256 KB |
Output is correct |
11 |
Correct |
1 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
7 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
256 KB |
Output is correct |
4 |
Correct |
4 ms |
376 KB |
Output is correct |
5 |
Correct |
3 ms |
380 KB |
Output is correct |
6 |
Correct |
4 ms |
384 KB |
Output is correct |
7 |
Correct |
8 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
384 KB |
Output is correct |
2 |
Correct |
38 ms |
504 KB |
Output is correct |
3 |
Correct |
10 ms |
384 KB |
Output is correct |
4 |
Correct |
38 ms |
492 KB |
Output is correct |
5 |
Correct |
33 ms |
436 KB |
Output is correct |
6 |
Correct |
32 ms |
648 KB |
Output is correct |
7 |
Correct |
30 ms |
500 KB |
Output is correct |
8 |
Correct |
32 ms |
532 KB |
Output is correct |
9 |
Correct |
30 ms |
552 KB |
Output is correct |
10 |
Correct |
30 ms |
504 KB |
Output is correct |
11 |
Correct |
30 ms |
576 KB |
Output is correct |
12 |
Correct |
25 ms |
652 KB |
Output is correct |
13 |
Correct |
30 ms |
536 KB |
Output is correct |
14 |
Correct |
36 ms |
504 KB |
Output is correct |
15 |
Correct |
32 ms |
672 KB |
Output is correct |
16 |
Correct |
31 ms |
504 KB |
Output is correct |
17 |
Correct |
26 ms |
504 KB |
Output is correct |
18 |
Correct |
30 ms |
500 KB |
Output is correct |
19 |
Correct |
26 ms |
504 KB |
Output is correct |
20 |
Correct |
17 ms |
412 KB |
Output is correct |
21 |
Correct |
30 ms |
504 KB |
Output is correct |
22 |
Correct |
24 ms |
504 KB |
Output is correct |
23 |
Correct |
34 ms |
504 KB |
Output is correct |
24 |
Correct |
30 ms |
504 KB |
Output is correct |
25 |
Correct |
24 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
570 ms |
3512 KB |
Output is correct |
2 |
Correct |
578 ms |
3500 KB |
Output is correct |
3 |
Correct |
589 ms |
3448 KB |
Output is correct |
4 |
Correct |
566 ms |
3524 KB |
Output is correct |
5 |
Correct |
532 ms |
3392 KB |
Output is correct |
6 |
Correct |
465 ms |
3432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
492 ms |
3588 KB |
Output is correct |
2 |
Correct |
523 ms |
3564 KB |
Output is correct |
3 |
Correct |
572 ms |
3608 KB |
Output is correct |
4 |
Correct |
583 ms |
3956 KB |
Output is correct |
5 |
Correct |
511 ms |
3948 KB |
Output is correct |
6 |
Correct |
468 ms |
3576 KB |
Output is correct |
7 |
Correct |
611 ms |
4128 KB |
Output is correct |
8 |
Correct |
525 ms |
4000 KB |
Output is correct |
9 |
Correct |
434 ms |
3704 KB |
Output is correct |
10 |
Correct |
691 ms |
5560 KB |
Output is correct |
11 |
Correct |
623 ms |
4000 KB |
Output is correct |