#include<bits/stdc++.h>
using namespace std;
using pi = pair<int, int>;
const int dx[6] = {1, -1, 0, 0, 0, 0};
const int dy[6] = {0, 0, 1, -1, 0, 0};
const int dz[6] = {0, 0, 0, 0, 1, -1};
int n, m, k, q;
int query(int x, int y, int z = 1){
if(x <= 0 || x > n || y <= 0 || y > m || z <= 0 || z > k) return 0;
printf("? %d %d %d\n", x, y, z);
fflush(stdout);
int v; scanf("%d",&v); return v;
}
void report(int x, int y, int z){
printf("! %d %d %d\n", x, y, z);
fflush(stdout);
exit(0);
}
int global_max = 0;
pi attain_max;
void solve(int sx, int ex, int sy, int ey){
if(ex - sx <= 2 && ey - sy <= 2){
for(int i=sx; i<=ex; i++){
for(int j=sy; j<=ey; j++){
if(max({query(i-1, j), query(i, j-1), query(i+1, j), query(i, j+1)}) <= query(i, j)){
report(i, j, 1);
}
}
}
report(attain_max.first, attain_max.second, 1);
}
if(ex - sx <= ey - sy){
int m = (sy + ey) / 2;
int mx = -1, mxp = -1;
for(int i=sx; i<=ex; i++){
int v = query(i, m, 1);
if(mx < v){
mx = v;
mxp = i;
}
}
if(mx < global_max){
assert(attain_max.second != m);
if(attain_max.second < m) solve(sx, ex, sy, m - 1);
else solve(sx, ex, m + 1, ey);
return;
}
global_max = mx;
attain_max = pi(mxp, m);
// got something larger
if(mx < query(mxp, m+1, 1)){
global_max = query(mxp, m + 1, 1);
attain_max = pi(mxp, m + 1);
solve(sx, ex, m + 1, ey);
}
else if(mx < query(mxp, m-1, 1)){
global_max = query(mxp, m - 1, 1);
attain_max = pi(mxp, m - 1);
solve(sx, ex, sy, m - 1);
}
else report(mxp, m, 1);
}
else{
int m = (sx + ex) / 2;
int mx = -1, mxp = -1;
for(int i=sy; i<=ey; i++){
int v = query(m, i, 1);
if(mx < v){
mx = v;
mxp = i;
}
}
if(mx < global_max){
assert(attain_max.first != m);
if(attain_max.first < m) solve(sx, m-1, sy, ey);
else solve(m+1, ex, sy, ey);
return;
}
global_max = mx;
attain_max = pi(m, mxp);
// got something larger
if(mx < query(m+1, mxp, 1)){
global_max = query(m+1, mxp, 1);
attain_max = pi(m+1, mxp);
solve(m+1, ex, sy, ey);
}
else if(mx < query(m-1, mxp, 1)){
global_max = query(m-1, mxp, 1);
attain_max = pi(m-1, mxp);
solve(sx, m-1, sy, ey);
}
else report(m, mxp, 1);
}
}
int main(){
cin >> n >> m >> k >> q;
auto ok = [&](int x, int y, int z){
return 1 <= x && x <= n && 1 <= y && y <= m && 1 <= z && z <= k;
};
if(m == 1){
map<int, int> qr;
auto Do = [&](int x){
if(x <= 0 || x > n) return 0;
if(qr.find(x) != qr.end()) return qr[x];
else return qr[x] = query(x, 1, 1);
};
double GR = (1 + sqrt(5)) / 2;
int s = 1, e = n;
int lcache = -1, rcache = -1;
while(true){
int m1 = round(s + (e - s) / (GR + 1));
int m2 = round(s + (GR * (e - s)) / (GR + 1));
if(~lcache) m1 = lcache;
if(~rcache) m2 = rcache;
if(m1 == m2) break;
if(Do(m1) < Do(m2)){
s = m1;
lcache = m2;
rcache = -1;
}
else{
e = m2;
lcache = -1;
rcache = m1;
}
}
for(int i=s; i<=e; i++){
if(Do(i - 1) <= Do(i) && Do(i) >= Do(i+1)) report(i, 1, 1);
}
assert(0);
}
if(k == 1){
solve(1, n, 1, m);
}
int px = -1, py = -1, pz = -1, cur = 0;
for(int i=0; i<q/2; i++){
int vx = rand() % n + 1, vy = rand() % m + 1, vz = rand() % k + 1;
int val = query(vx, vy, vz);
if(val > cur){
cur = val;
tie(px, py, pz) = make_tuple(vx, vy, vz);
}
}
q = q - q / 2;
while(q >= 6){
int dir = -1;
for(int i=0; i<6; i++){
if(ok(px + dx[i], py + dy[i], pz + dz[i])){
q--;
int nval = query(px + dx[i], py + dy[i], pz + dz[i]);
if(nval > cur){
cur = nval;
dir = i;
}
}
}
if(dir == -1) report(px, py, pz);
else{
px += dx[dir];
py += dy[dir];
pz += dz[dir];
}
}
}
Compilation message
worm.cpp: In function 'int query(int, int, int)':
worm.cpp:14:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int v; scanf("%d",&v); return v;
~~~~~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
248 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
248 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
248 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
312 KB |
Output is correct |
6 |
Correct |
2 ms |
248 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
248 KB |
Output is correct |
9 |
Correct |
2 ms |
380 KB |
Output is correct |
10 |
Correct |
2 ms |
248 KB |
Output is correct |
11 |
Correct |
3 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
376 KB |
Output is correct |
2 |
Correct |
4 ms |
248 KB |
Output is correct |
3 |
Correct |
2 ms |
248 KB |
Output is correct |
4 |
Correct |
7 ms |
376 KB |
Output is correct |
5 |
Correct |
6 ms |
248 KB |
Output is correct |
6 |
Correct |
3 ms |
296 KB |
Output is correct |
7 |
Correct |
7 ms |
380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
376 KB |
Output is correct |
2 |
Correct |
30 ms |
376 KB |
Output is correct |
3 |
Correct |
5 ms |
248 KB |
Output is correct |
4 |
Correct |
26 ms |
376 KB |
Output is correct |
5 |
Correct |
16 ms |
248 KB |
Output is correct |
6 |
Correct |
27 ms |
384 KB |
Output is correct |
7 |
Correct |
24 ms |
248 KB |
Output is correct |
8 |
Correct |
29 ms |
248 KB |
Output is correct |
9 |
Correct |
33 ms |
248 KB |
Output is correct |
10 |
Correct |
27 ms |
248 KB |
Output is correct |
11 |
Correct |
30 ms |
252 KB |
Output is correct |
12 |
Correct |
24 ms |
248 KB |
Output is correct |
13 |
Correct |
10 ms |
248 KB |
Output is correct |
14 |
Correct |
26 ms |
248 KB |
Output is correct |
15 |
Correct |
29 ms |
376 KB |
Output is correct |
16 |
Correct |
28 ms |
376 KB |
Output is correct |
17 |
Correct |
10 ms |
248 KB |
Output is correct |
18 |
Correct |
28 ms |
248 KB |
Output is correct |
19 |
Correct |
72 ms |
248 KB |
Output is correct |
20 |
Correct |
19 ms |
248 KB |
Output is correct |
21 |
Correct |
28 ms |
248 KB |
Output is correct |
22 |
Correct |
26 ms |
248 KB |
Output is correct |
23 |
Correct |
27 ms |
292 KB |
Output is correct |
24 |
Correct |
28 ms |
420 KB |
Output is correct |
25 |
Correct |
27 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
348 ms |
376 KB |
Output is correct |
2 |
Correct |
432 ms |
248 KB |
Output is correct |
3 |
Correct |
267 ms |
380 KB |
Output is correct |
4 |
Correct |
441 ms |
248 KB |
Output is correct |
5 |
Correct |
424 ms |
376 KB |
Output is correct |
6 |
Correct |
400 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
386 ms |
248 KB |
Output is correct |
2 |
Correct |
293 ms |
376 KB |
Output is correct |
3 |
Correct |
454 ms |
376 KB |
Output is correct |
4 |
Correct |
579 ms |
376 KB |
Output is correct |
5 |
Correct |
497 ms |
376 KB |
Output is correct |
6 |
Correct |
278 ms |
248 KB |
Output is correct |
7 |
Correct |
597 ms |
300 KB |
Output is correct |
8 |
Correct |
431 ms |
304 KB |
Output is correct |
9 |
Correct |
693 ms |
308 KB |
Output is correct |
10 |
Correct |
543 ms |
376 KB |
Output is correct |
11 |
Correct |
665 ms |
304 KB |
Output is correct |