#include<bits/stdc++.h>
using namespace std;
map< pair<int, pair<int,int> >,int > seen;
int n,m,k,q;
mt19937 rng(42);
int mx_seen=0;
int mx_x=0;
int mx_y=0;
int ask(pair<int, pair<int,int> > now)
{
if(seen.count(now))return seen[now];
cout<<"? "<<now.first<<" "<<now.second.first<<" "<<now.second.second<<endl;
int ret;
cin>>ret;
if(mx_seen<ret)
{
mx_seen=ret;
mx_x=now.first;
mx_y=now.second.first;
}
seen[now]=ret;
return ret;
}
int ask_prep(int x,int y,int z)
{
if(x==0||x==n+1||y==0||y==m+1||z==0||z==k+1)return 0;
return ask({x,{y,z}});
}
int x_moves[6]={1,-1,0,0,0,0};
int y_moves[6]={0,0,1,-1,0,0};
int z_moves[6]={0,0,0,0,1,-1};
void print(int x,int y,int z)
{
cout<<"! "<<x<<" "<<y<<" "<<z<<endl;
exit(0);
}
const double phi=(sqrt(5)+1)/2;
void solve(int l,int r,int known)
{
//cout<<" solve "<<l<<" "<<r<<" "<<known<<endl;
if(l==r)print(l,1,1);
if(r-l<=5)
{
for(int i=l;i<=r;i++)
{
bool stop=1;
for(int j=0;j<2;j++)
{
int x_=i+x_moves[j];
if(1<=x_&&x_<=n)
{
if(ask_prep(i,1,1)<ask_prep(x_,1,1)){stop=0;break;}
}
}
if(stop)print(i,1,1);
}
}
int other;
if((l+r)/2>=known)
{
other=l+(r-l)/phi;
//cout<<"other= "<<other<<endl;
if(ask_prep(known,1,1)<ask_prep(other,1,1))solve(known,r,other);
else solve(l,other,known);
}
else
{
other=l+(r-l)/phi/phi;
//cout<<"other2= "<<other<<endl;
if(ask_prep(other,1,1)<ask_prep(known,1,1))solve(other,r,known);
else solve(l,known,other);
}
}
void solve_1()
{
int known=1+(n-1)/phi;
ask_prep(known,1,1);
solve(1,n,known);
}
void walk(pair<int, pair<int,int> > best)
{
while(1)
{
bool stop=1;
int x=best.first,y=best.second.first,z=best.second.second;
for(int i=0;i<6;i++)
{
int x_=x+x_moves[i];
int y_=y+y_moves[i];
int z_=z+z_moves[i];
if(1<=x_&&x_<=n&&1<=y_&&y_<=m&&1<=z_&&z_<=k)
{
pair<int, pair<int,int> > current={x_,{y_,z_}};
if(ask(current)>ask(best)){best=current;stop=0;}
}
}
if(stop)
{
print(best.first,best.second.first,best.second.second);
}
}
}
void test(int x,int y,int z)
{
for(int t=0;t<6;t++)
if(ask_prep(x,y,z)<ask_prep(x+x_moves[t],y+y_moves[t],z+z_moves[t]))return;
print(x,y,z);
}
void solve_rect(int x1,int y1,int x2,int y2)
{
//cout<<"solve_rect "<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<endl;
if(x2-x1<=2&&y2-y1<=2)
{
for(int x=x1;x<=x2;x++)
for(int y=y1;y<=y2;y++)
{
bool stop=1;
for(int t=0;t<4;t++)
{
int x_=x+x_moves[t];
int y_=y+y_moves[t];
if(ask_prep(x,y,1)<ask_prep(x_,y_,1))
{
stop=0;
t=4;
}
}
if(stop)print(x,y,1);
}
assert(0==1);
}
if(x2-x1+1<=y2-y1+1)
{
int av=(y1+y2)/2;
int best_x=x1;
for(int x=x1;x<=x2;x++)
{
if(ask_prep(best_x,av,1)<ask_prep(x,av,1))best_x=x;
}
ask_prep(best_x,av-1,1);
ask_prep(best_x,av+1,1);
test(best_x,av,1);
if(av+1<=mx_y)solve_rect(x1,av+1,x2,y2);
else solve_rect(x1,y1,x2,av);
}
else
{
int av=(x1+x2)/2;
int best_y=y1;
for(int y=y1;y<=y2;y++)
{
if(ask_prep(av,best_y,1)<ask_prep(av,y,1))best_y=y;
}
ask_prep(av-1,best_y,1);
ask_prep(av+1,best_y,1);
test(av,best_y,1);
if(av+1<=mx_x)solve_rect(av+1,y1,x2,y2);
else solve_rect(x1,y1,av,y2);
}
}
void solve_2()
{
solve_rect(1,1,n,m);
}
int main()
{
cin>>n>>m>>k>>q;
if(m==1&&k==1)
{
solve_1();
}
if(k==1)
{
solve_2();
assert(0==1);
}
pair<int, pair<int,int> > best;
for(int i=1;i<=q/2;i++)
{
int x=rng()%n+1;
int y=rng()%m+1;
int z=rng()%k+1;
pair<int, pair<int,int> > current={x,{y,z}};
if(i==1)best=current;
else if(ask(best)<ask(current))best=current;
}
walk(best);
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
256 KB |
Output is correct |
2 |
Correct |
5 ms |
256 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
256 KB |
Output is correct |
3 |
Correct |
5 ms |
256 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
256 KB |
Output is correct |
6 |
Correct |
5 ms |
256 KB |
Output is correct |
7 |
Correct |
5 ms |
256 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
256 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
384 KB |
Output is correct |
2 |
Correct |
9 ms |
384 KB |
Output is correct |
3 |
Correct |
6 ms |
256 KB |
Output is correct |
4 |
Correct |
11 ms |
384 KB |
Output is correct |
5 |
Correct |
11 ms |
384 KB |
Output is correct |
6 |
Correct |
7 ms |
384 KB |
Output is correct |
7 |
Correct |
9 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
384 KB |
Output is correct |
2 |
Correct |
29 ms |
504 KB |
Output is correct |
3 |
Correct |
12 ms |
384 KB |
Output is correct |
4 |
Correct |
33 ms |
760 KB |
Output is correct |
5 |
Correct |
30 ms |
508 KB |
Output is correct |
6 |
Correct |
37 ms |
504 KB |
Output is correct |
7 |
Correct |
33 ms |
504 KB |
Output is correct |
8 |
Correct |
31 ms |
504 KB |
Output is correct |
9 |
Correct |
33 ms |
468 KB |
Output is correct |
10 |
Correct |
35 ms |
504 KB |
Output is correct |
11 |
Correct |
31 ms |
508 KB |
Output is correct |
12 |
Correct |
33 ms |
504 KB |
Output is correct |
13 |
Correct |
34 ms |
504 KB |
Output is correct |
14 |
Correct |
36 ms |
508 KB |
Output is correct |
15 |
Correct |
34 ms |
548 KB |
Output is correct |
16 |
Correct |
32 ms |
504 KB |
Output is correct |
17 |
Correct |
33 ms |
504 KB |
Output is correct |
18 |
Correct |
36 ms |
632 KB |
Output is correct |
19 |
Correct |
34 ms |
504 KB |
Output is correct |
20 |
Correct |
27 ms |
504 KB |
Output is correct |
21 |
Correct |
34 ms |
504 KB |
Output is correct |
22 |
Correct |
21 ms |
508 KB |
Output is correct |
23 |
Correct |
33 ms |
504 KB |
Output is correct |
24 |
Correct |
34 ms |
504 KB |
Output is correct |
25 |
Correct |
32 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
464 ms |
3320 KB |
Output is correct |
2 |
Correct |
477 ms |
3504 KB |
Output is correct |
3 |
Correct |
481 ms |
3448 KB |
Output is correct |
4 |
Correct |
476 ms |
3428 KB |
Output is correct |
5 |
Correct |
481 ms |
3416 KB |
Output is correct |
6 |
Correct |
462 ms |
3528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
738 ms |
5112 KB |
Output is correct |
2 |
Correct |
733 ms |
5240 KB |
Output is correct |
3 |
Correct |
728 ms |
4984 KB |
Output is correct |
4 |
Correct |
846 ms |
6300 KB |
Output is correct |
5 |
Correct |
769 ms |
5204 KB |
Output is correct |
6 |
Correct |
733 ms |
5240 KB |
Output is correct |
7 |
Correct |
736 ms |
5368 KB |
Output is correct |
8 |
Correct |
915 ms |
6524 KB |
Output is correct |
9 |
Correct |
845 ms |
5880 KB |
Output is correct |
10 |
Correct |
847 ms |
5752 KB |
Output is correct |
11 |
Correct |
734 ms |
5020 KB |
Output is correct |