#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
typedef long double ld;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int next(int a, int b){
return uniform_int_distribution(a, b)(rng);
}
int n, m, k, q;
int query(int x = 1, int y = 1, int z = 1){
if(x < 1 || x > n || y < 1 || y > m || z < 1 || z > k) return 0;
printf("? %d %d %d\n", x, y, z);
fflush(stdout);
int rt;
scanf("%d", &rt);
return rt;
}
const ld rat = (ld(3)-sqrt(ld(5)))/2.0;
void solve1d(){
int l = 1, r = n;
int p = ld(n)*rat;
p = max(1, p);
int ls = query(p);
bool rev = 0;
bool brute = 0;
while(1){
if(brute || int(ld(r-l+1)*rat) == 1){
int mx = 0, ans = -1;
for(int i = l; i <= r; i++){
int x = query(i);
if(x > mx) mx = x, ans = i;
}
printf("! %d 1 1\n", ans);
fflush(stdout);
exit(0);
}
if(!rev){
int x = r-int(ld(r-l+1)*rat)+1;
if(x <= p){ brute = 1; continue; }
int X = query(x);
if(X <= ls) r = x, rev = 1;
else l = p, p = x, ls = X;
}
else{
int x = l+int(ld(r-l+1)*rat)-1;
if(x >= p){ brute = 1; continue; }
int X = query(x);
if(X <= ls) l = x, rev = 0;
else r = p, p = x, ls = X;
}
}
}
void solve2d(){
int l1 = 1, r1 = n, l2 = 1, r2 = m;
bool vert = 1;
pair<int, int> lsp = {-1, -1};
int ls = 0;
while(1){
if(vert){
int md = (l2+r2)/2;
int mx = 0, in = -1;
for(int i = l1; i <= r1; i++){
int x = query(i, md);
if(x > mx) mx = x, in = i;
}
if(ls > mx){
if(lsp.sc < md) r2 = md-1;
else l2 = md+1;
vert = 0;
continue;
}
int a = query(in, md-1), b = query(in, md+1);
if(max(a, b) <= mx){
printf("! %d %d 1\n", in, md);
fflush(stdout);
exit(0);
}
else if(a > b) r2 = md-1, ls = a, lsp = {in, md-1};
else l2 = md+1, ls = b, lsp = {in, md+1};
vert = 0;
}
else{
int md = (l1+r1)/2;
int mx = 0, in = -1;
for(int i = l2; i <= r2; i++){
int x = query(md, i);
if(x > mx) mx = x, in = i;
}
if(ls > mx){
if(lsp.f < md) r1 = md-1;
else l1 = md+1;
vert = 1;
continue;
}
int a = query(md-1, in), b = query(md+1, in);
if(max(a, b) <= mx){
printf("! %d %d 1\n", md, in);
fflush(stdout);
exit(0);
}
else if(a > b) r1 = md-1, ls = a, lsp = {md-1, in};
else l1 = md+1, ls = b, lsp = {md+1, in};
vert = 1;
}
}
}
void solve3d(){
int mx = 0, a = 1, b = 1, c = 1;
for(int i = 0; i < q/2; i++){
int x = next(1, n), y = next(1, m), z = next(1, k);
int cur = query(x, y, z);
if(cur > mx) mx = cur, a = x, b = y, c = z;
}
while(1){
int _mx = 0;
int x, y, z, cur;
cur = query(a+1, b, c);
if(cur > _mx) _mx = cur, x = a+1, y = b, z = c;
cur = query(a-1, b, c);
if(cur > _mx) _mx = cur, x = a-1, y = b, z = c;
cur = query(a, b+1, c);
if(cur > _mx) _mx = cur, x = a, y = b+1, z = c;
cur = query(a, b-1, c);
if(cur > _mx) _mx = cur, x = a, y = b-1, z = c;
cur = query(a, b, c+1);
if(cur > _mx) _mx = cur, x = a, y = b, z = c+1;
cur = query(a, b, c-1);
if(cur > _mx) _mx = cur, x = a, y = b, z = c-1;
if(_mx <= mx){
printf("! %d %d %d\n", a, b, c);
fflush(stdout);
exit(0);
}
else{
a = x, b = y, c = z, mx = _mx;
}
}
}
int main(){
scanf("%d %d %d %d", &n, &m, &k, &q);
if(m == 1 && k == 1) solve1d();
else if(k == 1) solve2d();
else solve3d();
}
Compilation message
worm.cpp: In function 'int query(int, int, int)':
worm.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
23 | scanf("%d", &rt);
| ~~~~~^~~~~~~~~~~
worm.cpp: In function 'int main()':
worm.cpp:167:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
167 | scanf("%d %d %d %d", &n, &m, &k, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
208 KB |
Output is correct |
2 |
Correct |
1 ms |
208 KB |
Output is correct |
3 |
Correct |
1 ms |
208 KB |
Output is correct |
4 |
Correct |
1 ms |
208 KB |
Output is correct |
5 |
Correct |
1 ms |
208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
208 KB |
Output is correct |
2 |
Correct |
1 ms |
208 KB |
Output is correct |
3 |
Correct |
1 ms |
208 KB |
Output is correct |
4 |
Correct |
1 ms |
208 KB |
Output is correct |
5 |
Correct |
1 ms |
208 KB |
Output is correct |
6 |
Correct |
1 ms |
208 KB |
Output is correct |
7 |
Correct |
1 ms |
208 KB |
Output is correct |
8 |
Correct |
1 ms |
208 KB |
Output is correct |
9 |
Correct |
1 ms |
208 KB |
Output is correct |
10 |
Correct |
1 ms |
208 KB |
Output is correct |
11 |
Correct |
1 ms |
208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
208 KB |
Output is correct |
2 |
Correct |
4 ms |
208 KB |
Output is correct |
3 |
Correct |
2 ms |
208 KB |
Output is correct |
4 |
Correct |
3 ms |
208 KB |
Output is correct |
5 |
Correct |
9 ms |
208 KB |
Output is correct |
6 |
Correct |
2 ms |
208 KB |
Output is correct |
7 |
Correct |
7 ms |
208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
208 KB |
Output is correct |
2 |
Correct |
32 ms |
208 KB |
Output is correct |
3 |
Correct |
11 ms |
208 KB |
Output is correct |
4 |
Correct |
19 ms |
208 KB |
Output is correct |
5 |
Correct |
12 ms |
256 KB |
Output is correct |
6 |
Correct |
30 ms |
208 KB |
Output is correct |
7 |
Correct |
29 ms |
208 KB |
Output is correct |
8 |
Correct |
28 ms |
208 KB |
Output is correct |
9 |
Correct |
14 ms |
208 KB |
Output is correct |
10 |
Correct |
31 ms |
208 KB |
Output is correct |
11 |
Correct |
36 ms |
208 KB |
Output is correct |
12 |
Correct |
26 ms |
208 KB |
Output is correct |
13 |
Correct |
31 ms |
208 KB |
Output is correct |
14 |
Correct |
20 ms |
208 KB |
Output is correct |
15 |
Correct |
21 ms |
208 KB |
Output is correct |
16 |
Correct |
23 ms |
208 KB |
Output is correct |
17 |
Correct |
13 ms |
208 KB |
Output is correct |
18 |
Correct |
25 ms |
208 KB |
Output is correct |
19 |
Correct |
26 ms |
208 KB |
Output is correct |
20 |
Correct |
16 ms |
208 KB |
Output is correct |
21 |
Correct |
34 ms |
208 KB |
Output is correct |
22 |
Correct |
31 ms |
208 KB |
Output is correct |
23 |
Correct |
15 ms |
208 KB |
Output is correct |
24 |
Correct |
28 ms |
208 KB |
Output is correct |
25 |
Correct |
34 ms |
224 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
280 ms |
208 KB |
Output is correct |
2 |
Correct |
497 ms |
208 KB |
Output is correct |
3 |
Correct |
403 ms |
208 KB |
Output is correct |
4 |
Correct |
405 ms |
208 KB |
Output is correct |
5 |
Correct |
453 ms |
208 KB |
Output is correct |
6 |
Correct |
379 ms |
208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
470 ms |
208 KB |
Output is correct |
2 |
Correct |
703 ms |
208 KB |
Output is correct |
3 |
Correct |
623 ms |
208 KB |
Output is correct |
4 |
Correct |
405 ms |
208 KB |
Output is correct |
5 |
Correct |
611 ms |
208 KB |
Output is correct |
6 |
Correct |
652 ms |
208 KB |
Output is correct |
7 |
Correct |
740 ms |
208 KB |
Output is correct |
8 |
Correct |
546 ms |
208 KB |
Output is correct |
9 |
Correct |
608 ms |
280 KB |
Output is correct |
10 |
Correct |
590 ms |
208 KB |
Output is correct |
11 |
Correct |
618 ms |
272 KB |
Output is correct |