This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#include <stdlib.h>
#include <map>
int __query(int x, int y, int z) {
printf("? %d %d %d\n", x, y, z);
fflush(stdout);
int ans = -1;
(void)scanf("%d", &ans);
if (ans == -1) exit(0);
return ans;
}
std::map<int, int> M;
int mw, mx, my, mz;
int query(int x, int y, int z) {
int t = x - 1 | y - 1 << 10 | z - 1 << 20;
if (M.find(t) == M.end()) {
int w = __query(x, y, z);
M[t] = w;
if (w > mw) {
mw = w;
mx = x;
my = y;
mz = z;
}
return w;
}
return M[t];
}
__attribute__((noreturn))
void guess(int x, int y, int z) {
printf("! %d %d %d\n", x, y, z);
exit(0);
}
const double p = 0.381966;
int px[6] = { 1, -1, 0, 0, 0, 0 };
int py[6] = { 0, 0, 1, -1, 0, 0 };
int pz[6] = { 0, 0, 0, 0, 1, -1 };
int main() {
int N, M, K, Q;
(void)scanf("%d %d %d %d", &N, &M, &K, &Q);
// TODO do something smart
if (M == 1) {
int L = 1, R = N;
int T = L * p + R * (1 - p) + .5;
while (L < R) {
if (T + T == L + R) T = L * (1 - p) + R * p + .236;
int T2 = L + R - T;
if (T > T2) {
int T3 = T;
T = T2;
T2 = T3;
}
if (query(T, 1, 1) > query(T2, 1, 1)) R = T2 - 1;
else {
L = T + 1;
T = T2;
}
}
guess(L, 1, 1);
}
if (K == 1) {
int i, m, T, L = 1, R = N, D = 1, U = M;
while (L < R || D < U) {
if (R - L > U - D) {
m = L + R >> 1;
for (i = D; i <= U; i++) query(m, i, 1);
if (mx == m) query(m + 1, my, 1);
if (mx > m) L = m + 1;
else R = m;
}
else {
m = D + U >> 1;
for (i = L; i <= R; i++) query(i, m, 1);
if (my == m) query(mx, m + 1, 1);
if (my > m) D = m + 1;
else U = m;
}
}
guess(L, D, 1);
}
int i, x, y, z, w = -1;
for (i = 0; i < Q / 5; i++) {
int tx = rand() % N + 1;
int ty = rand() % M + 1;
int tz = rand() % K + 1;
if (query(tx, ty, tz) > w) {
w = query(tx, ty, tz);
x = tx;
y = ty;
z = tz;
}
}
do {
for (i = 0; i < 6; i++) {
int tx = x + px[i], ty = y + py[i], tz = z + pz[i];
if (tx > 0 && tx <= N && ty > 0 && ty <= M && tz > 0 && tz <= K && query(tx, ty, tz) > query(x, y, z)) {
x = tx;
y = ty;
z = tz;
break;
}
}
} while (i < 6);
guess(x, y, z);
}
Compilation message (stderr)
worm.cpp: In function 'int query(int, int, int)':
worm.cpp:17:21: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
int t = x - 1 | y - 1 << 10 | z - 1 << 20;
~~^~~
worm.cpp:17:13: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
int t = x - 1 | y - 1 << 10 | z - 1 << 20;
~~^~~
worm.cpp:17:35: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
int t = x - 1 | y - 1 << 10 | z - 1 << 20;
~~^~~
worm.cpp: In function 'int main()':
worm.cpp:72:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
m = L + R >> 1;
~~^~~
worm.cpp:79:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
m = D + U >> 1;
~~^~~
worm.cpp:69:15: warning: unused variable 'T' [-Wunused-variable]
int i, m, T, L = 1, R = N, D = 1, U = M;
^
worm.cpp: In function 'int __query(int, int, int)':
worm.cpp:9:3: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
(void)scanf("%d", &ans);
^~~~~~~~~~~~~~~~~~~~~~~
worm.cpp: In function 'int main()':
worm.cpp:46:2: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
(void)scanf("%d %d %d %d", &N, &M, &K, &Q);
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
worm.cpp:111:8: warning: 'z' may be used uninitialized in this function [-Wmaybe-uninitialized]
guess(x, y, z);
~~~~~^~~~~~~~~
worm.cpp:111:8: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
worm.cpp:111:8: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |