#include <bits/stdc++.h>
using namespace std;
#define ldb double
map<array<int,3>,int> was;
int n,m,k,q;
int Ask(int i,int j,int k){
if(was.count({i,j,k}))return was[{i,j,k}];
if(i<1||j<1||k<1||i>n||j>m||k>::k)return 0;
printf("? %i %i %i\n",i,j,k);
fflush(stdout);
int b;scanf("%i",&b);
was[{i,j,k}]=b;
return b;
}
void Ans(int i,int j,int k){
printf("! %i %i %i\n",i,j,k);
fflush(stdout);
exit(0);
}
bool Check(int i,int j,int k){
int now=Ask(i,j,k);
for(int a=-1;a<=1;a+=2)
if(now<max({Ask(i+a,j,k),Ask(i,j+a,k),Ask(i,j,k+a)}))
return 0;
Ans(i,j,k);
return 1;
}
mt19937 rng(time(0));
const ldb f1=0.618,f2=0.382;
int main(){
scanf("%i %i %i %i",&n,&m,&k,&q);
if(m==1&&k==1){
int top=n,bot=1,mid1=round(f1*bot+f2*top),mid2=round(f2*bot+f1*top),las=0;
while(top-bot>=5){
if(mid1>=mid2){
mid1=round(f1*bot+f2*top),mid2=round(f2*bot+f1*top);
if(mid1>=mid2)break;
}
if(Ask(mid1,1,1)<Ask(mid2,1,1)){
bot=mid1+1;
tie(mid1,mid2)=make_pair(mid2,round(f2*bot+f1*top));
}else{
top=mid2-1;
tie(mid1,mid2)=make_pair(round(f1*bot+f2*top),mid1);
}
}
for(int i=bot;i<=top;i++)Check(i,1,1);
}else if(k==1){
int X1=1,X2=n,Y1=1,Y2=m,Xm,Ym,last=0;
pair<int,int> pre;
while(X1<=X2&&Y1<=Y2){
Xm=X1+X2>>1;
int mx=0,pos=0;
for(int i=Y1;i<=Y2;i++){
int now=Ask(Xm,i,1);
if(now>mx)mx=now,pos=i;
}
if(mx<last){
if(Xm-1>=pre.first)X2=Xm-1;
else X1=Xm+1;
}else{
if(Ask(Xm-1,pos,1)>mx){
X2=Xm-1;
pre={Xm-1,pos};
}else if(Ask(Xm+1,pos,1)>mx){
X1=Xm+1;
pre={Xm+1,pos};
}else Ans(Xm,pos,1);
last=mx;
}
Ym=Y1+Y2>>1;
mx=0,pos=0;
for(int i=X1;i<=X2;i++){
int now=Ask(i,Ym,1);
if(now>mx)mx=now,pos=i;
}
if(mx<last){
if(Ym-1>=pre.second)Y2=Ym-1;
else Y1=Ym+1;
}else{
if(Ask(pos,Ym-1,1)>mx){
Y2=Ym-1;
pre={pos,Ym-1};
}else if(Ask(pos,Ym+1,1)>mx){
Y1=Ym+1;
pre={pos,Ym+1};
}else Ans(pos,Ym,1);
last=mx;
}
}
}else{
int X,Y,Z,mx=0;
for(int i=1;i<=q/2;i++){
int x=rng()%n+1;
int y=rng()%m+1;
int z=rng()%k+1;
if(Ask(x,y,z)>mx){
mx=Ask(x,y,z);
X=x;
Y=y;
Z=z;
}
}
while(!Check(X,Y,Z)){
if(Ask(X+1,Y,Z)>Ask(X,Y,Z))X++;
else if(Ask(X-1,Y,Z)>Ask(X,Y,Z))X--;
else if(Ask(X,Y+1,Z)>Ask(X,Y,Z))Y++;
else if(Ask(X,Y-1,Z)>Ask(X,Y,Z))Y--;
else if(Ask(X,Y,Z+1)>Ask(X,Y,Z))Z++;
else if(Ask(X,Y,Z-1)>Ask(X,Y,Z))Z--;
}
}
return 0;
}
Compilation message
worm.cpp: In function 'int main()':
worm.cpp:33:71: warning: unused variable 'las' [-Wunused-variable]
33 | int top=n,bot=1,mid1=round(f1*bot+f2*top),mid2=round(f2*bot+f1*top),las=0;
| ^~~
worm.cpp:52:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
52 | Xm=X1+X2>>1;
| ~~^~~
worm.cpp:71:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
71 | Ym=Y1+Y2>>1;
| ~~^~~
worm.cpp: In function 'int Ask(int, int, int)':
worm.cpp:11:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
11 | int b;scanf("%i",&b);
| ~~~~~^~~~~~~~~
worm.cpp: In function 'int main()':
worm.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
31 | scanf("%i %i %i %i",&n,&m,&k,&q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
worm.cpp:110:28: warning: 'Z' may be used uninitialized in this function [-Wmaybe-uninitialized]
110 | else if(Ask(X,Y,Z-1)>Ask(X,Y,Z))Z--;
| ~~~^~~~~~~
worm.cpp:110:28: warning: 'Y' may be used uninitialized in this function [-Wmaybe-uninitialized]
worm.cpp:110:28: warning: 'X' may be used uninitialized in this function [-Wmaybe-uninitialized]
# |
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 |
256 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 |
3 ms |
384 KB |
Output is correct |
2 |
Correct |
6 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
7 ms |
512 KB |
Output is correct |
5 |
Correct |
6 ms |
384 KB |
Output is correct |
6 |
Correct |
4 ms |
384 KB |
Output is correct |
7 |
Correct |
6 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
384 KB |
Output is correct |
2 |
Correct |
23 ms |
504 KB |
Output is correct |
3 |
Correct |
11 ms |
384 KB |
Output is correct |
4 |
Correct |
26 ms |
504 KB |
Output is correct |
5 |
Correct |
30 ms |
504 KB |
Output is correct |
6 |
Correct |
20 ms |
504 KB |
Output is correct |
7 |
Correct |
27 ms |
504 KB |
Output is correct |
8 |
Correct |
29 ms |
504 KB |
Output is correct |
9 |
Correct |
32 ms |
504 KB |
Output is correct |
10 |
Correct |
28 ms |
632 KB |
Output is correct |
11 |
Correct |
25 ms |
508 KB |
Output is correct |
12 |
Correct |
26 ms |
504 KB |
Output is correct |
13 |
Correct |
24 ms |
504 KB |
Output is correct |
14 |
Correct |
17 ms |
500 KB |
Output is correct |
15 |
Correct |
36 ms |
504 KB |
Output is correct |
16 |
Correct |
30 ms |
504 KB |
Output is correct |
17 |
Correct |
29 ms |
504 KB |
Output is correct |
18 |
Correct |
26 ms |
504 KB |
Output is correct |
19 |
Correct |
28 ms |
504 KB |
Output is correct |
20 |
Correct |
16 ms |
384 KB |
Output is correct |
21 |
Correct |
32 ms |
504 KB |
Output is correct |
22 |
Correct |
29 ms |
504 KB |
Output is correct |
23 |
Correct |
26 ms |
504 KB |
Output is correct |
24 |
Correct |
30 ms |
716 KB |
Output is correct |
25 |
Correct |
28 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
430 ms |
3448 KB |
Output is correct |
2 |
Correct |
466 ms |
3588 KB |
Output is correct |
3 |
Correct |
464 ms |
3448 KB |
Output is correct |
4 |
Correct |
474 ms |
3448 KB |
Output is correct |
5 |
Correct |
475 ms |
3600 KB |
Output is correct |
6 |
Correct |
481 ms |
3428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
655 ms |
5240 KB |
Output is correct |
2 |
Correct |
700 ms |
5164 KB |
Output is correct |
3 |
Correct |
712 ms |
5120 KB |
Output is correct |
4 |
Correct |
813 ms |
5968 KB |
Output is correct |
5 |
Correct |
795 ms |
5368 KB |
Output is correct |
6 |
Correct |
690 ms |
5564 KB |
Output is correct |
7 |
Correct |
656 ms |
5172 KB |
Output is correct |
8 |
Correct |
835 ms |
5460 KB |
Output is correct |
9 |
Correct |
937 ms |
5816 KB |
Output is correct |
10 |
Correct |
815 ms |
5136 KB |
Output is correct |
11 |
Correct |
981 ms |
5940 KB |
Output is correct |