#include <bits/stdc++.h>
#define eb emplace_back
#define mt make_tuple
#define mp make_pair
#define F first
#define S second
#define printv(a, b) { \
for(auto pv : a) b << pv << " "; \
b << "\n"; \
}
using namespace std;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const int MAX = 1e9;
mt19937 rnd(48763);
int n, m, k;
map<tiii, int> _qry;
int cnt = 0;
int query(int x, int y, int z){
if(x <= 0 || x > n || y <= 0 || y > m || z <= 0 || z > k) return 0;
if(_qry.find(mt(x, y, z)) == _qry.end()){
cout << "? " << x << " " << y << " " << z << "\n" << flush;
int r = 0;
cin >> r;
if(r == -1) exit(0);
_qry[mt(x, y, z)] = r;
cnt++;
}
return _qry[mt(x, y, z)];
}
int findmx1(int y, int z){
int x = -1, mx = -1;
for(int i = 1; i <= n; i++){
int tmp = query(i, y, z);
if(tmp > mx) mx = tmp, x = i;
}
return x;
}
pii findmx2(int z){
int x = -1, y = -1, mx = -1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
int tmp = query(i, j, z);
if(tmp > mx) mx = tmp, x = i, y = j;
}
}
return mp(x, y);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int q;
cin >> n >> m >> k >> q;
int x, y, z;
if(m == 1 && k == 1){
int l = 1, r = n;
while(l < r){
int mid = (l + r) / 2;
query(mid, 1, 1);
query(mid + 1, 1, 1);
//cerr << l << " " << r << " " << mid << " " << query(mid, 1, 1) << " " << query(mid + 1, 1, 1) << "\n";
if(query(mid, 1, 1) < query(mid + 1, 1, 1)) l = mid + 1;
else r = mid;
}
x = l; y = 1; z = 1;
}
else if(k == 1){
int x = -1, y = -1, z = -1;
{
int l = 1, r = k;
while(l < r){
int mid = (l + r) / 2;
int x, y;
tie(x, y) = findmx2(mid);
if(query(x, y, mid + 1) >= query(x, y, mid)) l = mid + 1;
else if(query(x, y, mid - 1) >= query(x, y, mid)) r = mid - 1;
else l = r = mid;
}
z = l;
}
{
int l = 1, r = m;
while(l < r){
int mid = (l + r) / 2;
int x = findmx1(mid, z);
if(query(x, mid + 1, z) >= query(x, mid, z)) l = mid + 1;
else if(query(x, mid - 1, z) >= query(x, mid, z)) r = mid - 1;
else l = r = mid;
}
y = l;
}
x = findmx1(y, z);
//cerr << cnt << "\n";
cout << "! " << x << " " << y << " " << z << "\n" << flush;
return 0;
}
else{
int l = 1, r = k;
while(l < r){
int mid = (l + r) / 2;
int x, y;
tie(x, y) = findmx2(mid);
if(query(x, y, mid + 1) >= query(x, y, mid)) l = mid + 1;
else if(query(x, y, mid - 1) >= query(x, y, mid)) r = mid - 1;
else l = r = mid;
}
z = l;
tie(x, y) = findmx2(z);
}
cout << "! " << x << " " << y << " " << z << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
200 KB |
Output is correct |
2 |
Correct |
1 ms |
200 KB |
Output is correct |
3 |
Correct |
1 ms |
200 KB |
Output is correct |
4 |
Correct |
1 ms |
200 KB |
Output is correct |
5 |
Correct |
1 ms |
200 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
200 KB |
too many queries. input: ? 499998 1 1 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
504 KB |
Output is correct |
2 |
Correct |
8 ms |
344 KB |
Output is correct |
3 |
Correct |
22 ms |
360 KB |
Output is correct |
4 |
Correct |
16 ms |
328 KB |
Output is correct |
5 |
Correct |
15 ms |
328 KB |
Output is correct |
6 |
Correct |
2 ms |
320 KB |
Output is correct |
7 |
Correct |
15 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
34 ms |
512 KB |
too many queries. input: ? 498 938 1 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
572 ms |
4644 KB |
Output is correct |
2 |
Correct |
585 ms |
3968 KB |
Output is correct |
3 |
Correct |
604 ms |
4932 KB |
Output is correct |
4 |
Correct |
422 ms |
4572 KB |
Output is correct |
5 |
Correct |
551 ms |
4096 KB |
Output is correct |
6 |
Correct |
504 ms |
3992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1285 ms |
9632 KB |
too many queries. input: ? 301 1 250 |
2 |
Halted |
0 ms |
0 KB |
- |