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 <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;
int n, m, k, q, a;
int ask(int x = 1, int y = 1, int z = 1) {
static map<llong, int> mp;
if (x <= 0) return 0;
if (y <= 0) return 0;
if (z <= 0) return 0;
if (x > n) return 0;
if (y > m) return 0;
if (z > k) return 0;
llong v = x + y * (n + 5ll) + z * (n + 5ll) * (m + 5ll);
if (mp.find(v) != mp.end()) return mp[v];
if (q < ++a) exit(1);
int r;
printf("? %d %d %d\n", x, y, z);
fflush(stdout);
scanf("%d", &r);
return mp[v] = r;
}
void answer(int x = 1, int y = 1, int z = 1) {
printf("! %d %d %d\n", x, y, z);
exit(0);
}
int gox[6] = { 1, -1, 0, 0, 0, 0 };
int goy[6] = { 0, 0, 1, -1, 0, 0 };
int goz[6] = { 0, 0, 0, 0, 1, -1 };
int checkLocalMin(int x = 1, int y = 1, int z = 1) {
for (int i = 0; i < 6; ++i) {
if (ask(x, y, z) < ask(x + gox[i], y + goy[i], z + goz[i])) return 0;
}
return 1;
}
int main() {
scanf("%d%d%d%d", &n, &m, &k, &q);
if (k > 1) {
srand(time(0));
int x = (n + 1) / 2;
int y = (m + 1) / 2;
int z = (k + 1) / 2;
int it = q / 2;
while (it--) {
int mx = rand() % n + 1;
int my = rand() % m + 1;
int mz = rand() % k + 1;
if (ask(x, y, z) < ask(mx, my, mz)) x = mx, y = my, z = mz;
}
while (1) {
vector<int> ch = { 0, 1, 2, 3, 4, 5 };
random_shuffle(ch.begin(), ch.end());
int c = 0;
for (int i : ch) {
if (ask(x, y, z) < ask(x + gox[i], y + goy[i], z + goz[i])) {
x += gox[i];
y += goy[i];
z += goz[i];
c = 1;
break;
}
}
if (c) continue;
answer(x, y, z);
}
}
else if (m > 1) {
int sx = 1, ex = n;
int sy = 1, ey = m;
int mx = 0, my = 0, mv = 0;
while (sx < ex || sy < ey) {
if (ex - sx < ey - sy) {
int md = (sy + ey) / 2;
if (md == my) ++md;
int mxv = 0, mxi = 0;
for (int i = sx; i <= ex; ++i) {
if (mxv < ask(i, md)) mxv = ask(i, md), mxi = i;
}
if (mv < mxv) {
int l = ask(mxi, md - 1);
int r = ask(mxi, md + 1);
if (l <= mxv && r <= mxv) answer(mxi, md);
mx = mxi;
if (l > r) ey = max(md - 1, sy), my = md - 1, mv = l;
else sy = min(md + 1, ey), my = md + 1, mv = r;
}
else {
if (my < md) ey = max(md - 1, sy);
else sy = min(md + 1, ey);
}
}
else {
int md = (sx + ex) / 2;
if (md == mx) ++md;
int mxv = 0, mxi = 0;
for (int i = sy; i <= ey; ++i) {
if (mxv < ask(md, i)) mxv = ask(md, i), mxi = i;
}
if (mv < mxv) {
int l = ask(md - 1, mxi);
int r = ask(md + 1, mxi);
if (l <= mxv && r <= mxv) answer(md, mxi);
my = mxi;
if (l > r) ex = max(md - 1, sx), mx = md - 1, mv = l;
else sx = min(md + 1, ex), mx = md + 1, mv = r;
}
else {
if (mx < md) ex = max(md - 1, sx);
else sx = min(md + 1, ex);
}
}
}
answer(mx, my);
}
else {
int s = 1, e = n;
const double p = 0.382;
int l = (1 - p) * s + p * e;
int r = s + e - l;
while (s < e) {
if (ask(l) < ask(r)) s = l + 1, l = r, r = max(p * s + (1 - p) * e, l + 1.0);
else e = r - 1, r = l, l = min((1 - p) * s + p * e, r - 1.0);
}
answer(s);
}
return 0;
}
Compilation message (stderr)
worm.cpp: In function 'int ask(int, int, int)':
worm.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &r);
~~~~~^~~~~~~~~~
worm.cpp: In function 'int main()':
worm.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &n, &m, &k, &q);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |