Submission #623659

#TimeUsernameProblemLanguageResultExecution timeMemory
623659KoDWorm Worries (BOI18_worm)C++17
44 / 100
28 ms496 KiB
#include <bits/stdc++.h> using std::vector; using std::pair; using std::tuple; using std::array; template <class F> struct fixed : private F { explicit fixed(F&& f) : F(std::forward<F>(f)) {} template <class... Args> decltype(auto) operator()(Args&&... args) const { return F::operator()(*this, std::forward<Args>(args)...); } }; int N, M, K, Q; bool inside(const int x, const int y, const int z) { return 1 <= x and x <= N and 1 <= y and y <= M and 1 <= z and z <= K; } int query(const int x, const int y, const int z) { static std::map<array<int, 3>, int> memo = {}; if (inside(x, y, z)) { auto& ret = memo[{x, y, z}]; if (ret == 0) { std::cout << "? " << x << " " << y << " " << z << std::endl; std::cin >> ret; } return ret; } else { return 0; } } void answer(const int x, const int y, const int z) { assert(inside(x, y, z)); std::cout << "! " << x << " " << y << " " << z << std::endl; std::exit(EXIT_SUCCESS); } void solve_1D() { int l = 0, r = N + 1; int x = 1, y = 1; while (l + y < r) { x += y; std::swap(x, y); } r = l + y; while (x > 1) { y -= x; if (query(l + y, 1, 1) < query(r - y, 1, 1)) { l += y; } else { r -= y; } std::swap(x, y); } answer(l + x, 1, 1); } void solve_2D() { fixed([&](auto&& dfs, const int i0, const int i1, const int j0, const int j1) -> void { if (i1 - i0 > j0 - j1) { const int i = (i0 + i1) / 2; int j = 0, fj = 0; for (int k = j0; k <= j1; ++k) { const int fk = query(i, k, 1); if (fj < fk) { j = k; fj = fk; } } if (fj < query(i - 1, j, 1)) { dfs(i0, i - 1, j0, j1); } else if (fj < query(i + 1, j, 1)) { dfs(i + 1, i1, j0, j1); } else { answer(i, j, 1); } } else { const int j = (j0 + j1) / 2; int i = 0, fi = 0; for (int k = i0; k <= i1; ++k) { const int fk = query(k, j, 1); if (fi < fk) { i = k; fi = fk; } } if (fi < query(i, j - 1, 1)) { dfs(i0, i1, j0, j - 1); } else if (fi < query(i, j + 1, 1)) { dfs(i0, i1, j + 1, j1); } else { answer(i, j, 1); } } })(1, N, 1, M); } void solve_3D() { } int main() { std::cin >> N >> M >> K >> Q; if (M == 1 and K == 1) { solve_1D(); } else if (K == 1) { solve_2D(); } else { solve_3D(); } }
#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...