/* https://boi2018.progolymp.se/spoiler-day1.pdf */
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
int n,m,k,q;
map<array<int,3>,int> val;
int ask(int x,int y,int z) {
if (x<1||x>n||y<1||y>m||z<1||z>k) return 0;
if (!val.count({x,y,z})) {
printf("? %d %d %d\n",x,y,z);
fflush(stdout);
scanf("%d",&val[{x,y,z}]);
}
return val[{x,y,z}];
}
bool good(int x,int y,int z){
if(x<1||x>n||y<1||y>m||z<1||z>k) return false;
if (ask(x,y,z)<ask(x+1,y,z)) return false;
if (ask(x,y,z)<ask(x,y+1,z)) return false;
if (ask(x,y,z)<ask(x,y,z+1)) return false;
if (ask(x,y,z)<ask(x-1,y,z)) return false;
if (ask(x,y,z)<ask(x,y-1,z)) return false;
if (ask(x,y,z)<ask(x,y,z-1)) return false;
return true;
}
int main() {
scanf("%d%d%d%d",&n,&m,&k,&q);
if (m==1&&k==1) {
int l=1,r=n,x=0.618*l+0.382*r,y=0.382*l+0.618*r;
while (l+10<r) {
if (x>=y) {
x=0.618*l+0.382*r;
y=0.382*l+0.618*r;
if(x>=y) break;
}
if (ask(x,1,1)<ask(y,1,1)) {
l=x+1; x=y; y=0.382*l+0.618*r;
} else {
r=y-1; y=x; x=0.618*l+0.382*r;
}
}
int ans=l;
rep(i,l,r+1) if (good(i,1,1)) ans=i;
printf("! %d 1 1",ans);
fflush(stdout);
return 0;
}
if (k==1) {
int lx=1,rx=n,ly=1,ry=m,f=0,val=0;
PII p=mp(-1,-1);
while (lx<rx||ly<ry) {
if (f==0) {
int mid=(lx+rx)/2;
int pos=ly;
rep(i,ly,ry+1) {
if (ask(mid,pos,1)<ask(mid,i,1)) {
pos=i;
}
}
if (good(mid,pos,1)) {
printf("! %d %d 1",mid,pos);
fflush(stdout);
return 0;
}
if (ask(mid,pos,1)<val) {
if (p.fi<mid) rx=mid-1;
else lx=mid+1;
} else {
p=mp(mid,pos);
val=ask(mid,pos,1);
int l=ask(mid-1,pos,1);
int r=ask(mid+1,pos,1);
if (l>r) rx=mid-1; else lx=mid+1;
}
} else {
int mid=(ly+ry)/2;
int pos=lx;
rep(i,lx,rx+1) {
if (ask(pos,mid,1)<ask(i,mid,1)) {
pos=i;
}
}
if (good(pos,mid,1)) {
printf("! %d %d 1",pos,mid);
fflush(stdout);
return 0;
}
if (ask(pos,mid,1)<val) {
if (p.se<mid) ry=mid-1;
else ly=mid+1;
} else {
p=mp(pos,mid);
val=ask(pos,mid,1);
int l=ask(pos,mid-1,1);
int r=ask(pos,mid+1,1);
if (l>r) ry=mid-1; else ly=mid+1;
}
}
f^=1;
}
printf("! %d %d 1",lx,ly);
fflush(stdout);
return 0;
}
int x=1,y=1,z=1,mx=0;
rep(iter,0,q/2) {
int a=rnd(n)+1;
int b=rnd(m)+1;
int c=rnd(k)+1;
int v=ask(a,b,c);
if (v>mx) mx=v,x=a,y=b,z=c;
}
while (!good(x,y,z)) {
array<int,4> move={mx,x,y,z};
move=max(move,{ask(x-1,y,z),x-1,y,z});
move=max(move,{ask(x,y-1,z),x,y-1,z});
move=max(move,{ask(x,y,z-1),x,y,z-1});
move=max(move,{ask(x+1,y,z),x+1,y,z});
move=max(move,{ask(x,y+1,z),x,y+1,z});
move=max(move,{ask(x,y,z+1),x,y,z+1});
mx=move[0]; x=move[1]; y=move[2]; z=move[3];
}
printf("! %d %d %d",x,y,z);
fflush(stdout);
}
Compilation message
worm.cpp: In function 'int ask(int, int, int)':
worm.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
33 | scanf("%d",&val[{x,y,z}]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
worm.cpp: In function 'int main()':
worm.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
50 | scanf("%d%d%d%d",&n,&m,&k,&q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
444 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
440 KB |
Output is correct |
5 |
Correct |
0 ms |
356 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
440 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
440 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
688 KB |
Output is correct |
6 |
Correct |
1 ms |
444 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
436 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
436 KB |
Output is correct |
2 |
Correct |
4 ms |
956 KB |
Output is correct |
3 |
Correct |
1 ms |
440 KB |
Output is correct |
4 |
Correct |
3 ms |
692 KB |
Output is correct |
5 |
Correct |
3 ms |
960 KB |
Output is correct |
6 |
Correct |
1 ms |
444 KB |
Output is correct |
7 |
Correct |
3 ms |
700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
692 KB |
Output is correct |
2 |
Correct |
13 ms |
692 KB |
Output is correct |
3 |
Correct |
5 ms |
700 KB |
Output is correct |
4 |
Correct |
17 ms |
1256 KB |
Output is correct |
5 |
Correct |
13 ms |
1288 KB |
Output is correct |
6 |
Correct |
14 ms |
1520 KB |
Output is correct |
7 |
Correct |
22 ms |
756 KB |
Output is correct |
8 |
Correct |
13 ms |
988 KB |
Output is correct |
9 |
Correct |
12 ms |
1232 KB |
Output is correct |
10 |
Correct |
15 ms |
784 KB |
Output is correct |
11 |
Correct |
13 ms |
1504 KB |
Output is correct |
12 |
Correct |
14 ms |
1516 KB |
Output is correct |
13 |
Correct |
17 ms |
1320 KB |
Output is correct |
14 |
Correct |
18 ms |
1232 KB |
Output is correct |
15 |
Correct |
14 ms |
2012 KB |
Output is correct |
16 |
Correct |
15 ms |
1528 KB |
Output is correct |
17 |
Correct |
15 ms |
972 KB |
Output is correct |
18 |
Correct |
16 ms |
1220 KB |
Output is correct |
19 |
Correct |
14 ms |
952 KB |
Output is correct |
20 |
Correct |
10 ms |
1480 KB |
Output is correct |
21 |
Correct |
19 ms |
1540 KB |
Output is correct |
22 |
Correct |
16 ms |
1208 KB |
Output is correct |
23 |
Correct |
13 ms |
948 KB |
Output is correct |
24 |
Correct |
13 ms |
1548 KB |
Output is correct |
25 |
Correct |
14 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
283 ms |
5036 KB |
Output is correct |
2 |
Correct |
310 ms |
4716 KB |
Output is correct |
3 |
Correct |
331 ms |
4116 KB |
Output is correct |
4 |
Correct |
278 ms |
4288 KB |
Output is correct |
5 |
Correct |
269 ms |
4232 KB |
Output is correct |
6 |
Correct |
305 ms |
4376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
464 ms |
6140 KB |
Output is correct |
2 |
Correct |
499 ms |
6112 KB |
Output is correct |
3 |
Correct |
490 ms |
5588 KB |
Output is correct |
4 |
Correct |
499 ms |
7012 KB |
Output is correct |
5 |
Correct |
538 ms |
6656 KB |
Output is correct |
6 |
Correct |
494 ms |
6828 KB |
Output is correct |
7 |
Correct |
462 ms |
6288 KB |
Output is correct |
8 |
Correct |
484 ms |
6768 KB |
Output is correct |
9 |
Correct |
485 ms |
6368 KB |
Output is correct |
10 |
Correct |
501 ms |
5980 KB |
Output is correct |
11 |
Correct |
613 ms |
6668 KB |
Output is correct |