제출 #250929

#제출 시각아이디문제언어결과실행 시간메모리
250929imeimi2000Worm Worries (BOI18_worm)C++17
100 / 100
974 ms5752 KiB
#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; }

컴파일 시 표준 에러 (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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...