| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1259989 | patgra | Worm Worries (BOI18_worm) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))
constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl
#define ll long long
#define pb push_back
#define ld long double
using namespace std;
constexpr bool readit = 0;
vector<vector<vector<int>>> heights;
int N, M, K, Q, ogq;
int query(int x, int y, int z) {
if(x < 0 || x >= N || y < 0 || y >= M || z < 0 || z >= K) return -1;
if(heights[x][y][z] != -1) return heights[x][y][z];
//if(!Q) return -1;
printf("? %d %d %d\n", x + 1, y + 1, z + 1);
fflush(stdout);
Q--;
int ans = -1;
(void)scanf("%d", &ans);
if (ans == -1) exit(0);
heights[x][y][z] = ans;
return ans;
}
bool tryit(int x, int y, int z) {
return (x == 0 || query(x, y, z) >= query(x - 1, y, z)) &&
(x == N - 1 || query(x, y, z) >= query(x + 1, y, z)) &&
(y == 0 || query(x, y, z) >= query(x, y - 1, z)) &&
(y == M - 1 || query(x, y, z) >= query(x, y + 1, z)) &&
(z == 0 || query(x, y, z) >= query(x, y, z - 1)) &&
(z == K - 1 || query(x, y, z) >= query(x, y, z + 1));
}
void guess(int x, int y, int z) {
x++, y++, z++;
printf("! %d %d %d\n", x, y, z);
x--, y--, z--;
if constexpr(readit) assert((x == 0 || heights[x][y][z] >= heights[x - 1][y][z]) &&
(x == N - 1 || heights[x][y][z] >= heights[x + 1][y][z]) &&
(y == 0 || heights[x][y][z] >= heights[x][y - 1][z]) &&
(y == M - 1 || heights[x][y][z] >= heights[x][y + 1][z]) &&
(z == 0 || heights[x][y][z] >= heights[x][y][z - 1]) &&
(z == K - 1 || heights[x][y][z] >= heights[x][y][z + 1]));
exit(0);
}
int main() {
(void)scanf("%d %d %d %d", &N, &M, &K, &Q);
ogq = Q;
heights.resize(N, vector<vector<int>>(M, vector<int>(K, -1)));
if constexpr(readit) rep(i, 0, N) rep(j, 0, M) rep(k, 0, K) scanf("%d", &heights[i][j][k]);
if(Q == 35) {
int l = 0, r = N - 1;
int m1 = -1, m2 = -1;
int vm1 = -1, vm2 = -1;
double ratio = 0.38197;
while(r - l + 1 > 3) {
if(m1 < l || m1 > r) {
m1 = (int)ceil(ratio * (r - l + 1)) + l;
if(m1 == m2) m1--;
if(m1 < l) m1 += 2;
vm1 = query(m1, 0, 0);
}
if(m2 < l || m2 > r) {
m2 = r - (int)ceil(ratio * (r - l + 1));
if(m2 == m1) m2++;
if(m2 > r) m2 -= 2
vm2 = query(m2, 0, 0);
}
if(m1 > m2) swap(m1, m2), swap(vm1, vm2);
if(vm1 > vm2) {
r = m2;
m2 = m1;
vm2 = vm1;
m1 = -1;
vm1 = -1;
}
else {
l = m1;
m1 = m2;
vm1 = vm2;
m2 = -1;
vm2 = -1;
}
}
if(r - l == 0) guess(l, 0, 0);
if(r - l == 1) {
if(query(l, 0, 0) < query(r, 0, 0)) guess(r, 0, 0);
else if(query(l, 0, 0) > query(r, 0, 0)) guess(l, 0, 0);
else if(l == 0) guess(l, 0, 0);
else if(r == N - 1) guess(r, 0, 0);
else if(query(l, 0, 0) >= query(l - 1, 0, 0)) guess(l, 0, 0);
else guess(r, 0, 0);
}
if(r - l == 2) {
if(query(l, 0, 0) < query(l + 1, 0, 0) && query(r, 0, 0) < query(l + 1, 0, 0)) guess(l + 1, 0, 0);
else if(query(l, 0, 0) >= query(l + 1, 0, 0)) {
if(l == 0 || query(l - 1, 0, 0) < query(l, 0, 0)) guess(l, 0, 0);
else guess(r, 0, 0);
}
else {
if(query(r, 0, 0) > query(l + 1, 0, 0)) guess(r, 0, 0);
else guess(l + 1, 0, 0);
}
}
return 0;
}
mt19937 rnd(2137 * N + Q);
array<int, 4> mx = {{-1, 0, 0, 0}};
while(Q * 2 > ogq) {
int x = rnd() % N, y = rnd() % M, z = rnd() % K;
mx = max(mx, {{query(x, y, z), x, y, z}});
if(ogq - Q == N * M * K) break;
}
int x = mx[1], y = mx[2], z = mx[3];
while(Q) {
mx = max(mx, {{query(x + 1, y, z), x + 1, y, z}});
if(!Q) break;
mx = max(mx, {{query(x - 1, y, z), x - 1, y, z}});
if(!Q) break;
mx = max(mx, {{query(x, y + 1, z), x, y + 1, z}});
if(!Q) break;
mx = max(mx, {{query(x, y - 1, z), x, y - 1, z}});
if(!Q) break;
mx = max(mx, {{query(x, y, z + 1), x, y, z + 1}});
if(!Q) break;
mx = max(mx, {{query(x, y, z - 1), x, y, z - 1}});
if(mx[0] == query(x, y, z)) break;
x = mx[1], y = mx[2], z = mx[3];
}
guess(x, y, z);
}