Submission #676813

#TimeUsernameProblemLanguageResultExecution timeMemory
676813CyanmondWorm Worries (BOI18_worm)C++17
47 / 100
482 ms3316 KiB
#include <bits/stdc++.h> std::map<std::tuple<int, int, int>, int> memo; int W; int query(int x, int y = 0, int z = 0) { if (std::min({x, y, z}) < 0 or std::max({x, y, z}) >= W) { return 0; } if (memo.find({x, y, z}) != memo.end()) { return memo[{x, y, z}]; } std::cout << '?' << ' ' << x + 1 << ' ' << y + 1 << ' ' << z + 1 << std::endl; int res; std::cin >> res; if (res == -1) { std::exit(0); } memo[{x, y, z}] = res; return res; } int finish(int x, int y = 0, int z = 0) { std::cout << '!' << ' ' << x + 1 << ' ' << y + 1 << ' ' << z + 1 << std::endl; std::exit(0); } void solve1() { int l = 0, r = W; while (r - l > 1) { auto mid = (l + r) / 2; const int lm_val = query(mid - 1), rm_val = query(mid); if (lm_val > rm_val) { r = mid; } else { l = mid; } } finish(l); } void solve2() { int xl = 0, xr = W, yl = 0, yr = W; while (std::max(xr - xl, yr - yl) > 1) { if (yr - yl > 1) { const auto ym = (yl + yr) / 2; int ma = -1, ma_id = -1; for (int i = xl; i < xr; ++i) { const int v = query(i, ym); if (v > ma) { ma = v; ma_id = i; } } const int v2 = query(ma_id, ym - 1); if (v2 > ma) { yr = ym; } else { yl = ym; } } if (xr - xl > 1) { const auto xm = (xl + xr) / 2; int ma = -1, ma_id = -1; for (int i = yl; i < yr; ++i) { const int v = query(xm, i); if (v > ma) { ma = v; ma_id = i; } } const int v2 = query(xm - 1, ma_id); if (v2 > ma) { xr = xm; } else { xl = xm; } } } finish(xl, yl); } constexpr std::array<std::tuple<int, int, int>, 6> dxyz = {{{0, 0, 1}, {0, 0, -1}, {0, 1, 0}, {0, -1, 0}, {1, 0, 0}, {-1, 0, 0}}}; void solve3(int Q) { int best = -1; int x = 0, y = 0, z = 0; std::random_device seed_gen; std::mt19937 engine(seed_gen()); std::uniform_int_distribution dist(0, W); for (int i = 0; i < Q / 6; ++i) { --Q; const int nx = dist(engine), ny = dist(engine), nz = dist(engine); const int v = query(nx, ny, nz); if (v > best) { best = v; x = nx, y = ny, z = nz; } } while (Q > 0) { for (const auto &[ax, ay, az] : dxyz) { if (Q == 0) { break; } --Q; const auto nx = x + ax, ny = y + ay, nz = z + az; if (std::min({nx, ny, nz}) < 0 or std::max({nx, ny, nz}) >= W) { continue; } const int v = query(nx, ny, nz); if (v > best) { best = v; x = nx, y = ny, z = nz; break; } } } finish(x, y, z); } int main() { int N, M, K, Q; std::cin >> N >> M >> K >> Q; W = N; if (M == 1) { solve1(); } else if (K == 1) { solve2(); } else { solve3(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...