#include #include #include #include #include #include #include #include #include #include // #include "Src/Number/IntegerDivision.hpp" #include #include namespace zawa { using i16 = std::int16_t; using i32 = std::int32_t; using i64 = std::int64_t; using i128 = __int128_t; using u8 = std::uint8_t; using u16 = std::uint16_t; using u32 = std::uint32_t; using u64 = std::uint64_t; using usize = std::size_t; } // namespace zawa #include #include #include namespace zawa { namespace internal { template T MidPoint(T a, T b) { if (a > b) std::swap(a, b); return a + ((b - a) >> 1); } template T Abs(T a, T b) { return (a >= b ? a - b : b - a); } } // namespace zawa::internal template T BinarySearch(T ok, T ng, const Function& f) { static_assert(std::is_integral_v, "T must be integral type"); static_assert(std::is_convertible_v>, "f must be function bool(T)"); while (internal::Abs(ok, ng) > 1) { T mid{ internal::MidPoint(ok, ng) }; (f(mid) ? ok : ng) = mid; } return ok; } template T BinarySearch(T ok, T ng, const Function& f, u32 upperLimit) { static_assert(std::is_signed_v, "T must be signed arithmetic type"); static_assert(std::is_convertible_v>, "f must be function bool(T)"); for (u32 _{} ; _ < upperLimit ; _++) { T mid{ (ok + ng) / (T)2 }; (f(mid) ? ok : ng) = mid; } return ok; } } // namespace zawa // #include "Src/Sequence/CompressedSequence.hpp" // #include "Src/Sequence/RunLengthEncoding.hpp" // #include "Src/Algebra/Group/AdditiveGroup.hpp" // #include "Src/DataStructure/FenwickTree/FenwickTree.hpp" // #include "Src/DataStructure/SegmentTree/SegmentTree.hpp" // #include "Src/DataStructure/DisjointSetUnion/DisjointSetUnion.hpp" // #include "Src/DataStructure/Heap/BinaryHeap.hpp" namespace zawa {} using namespace zawa; // #include "atcoder/modint" // using mint = atcoder::modint998244353; // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #include // #pragma GCC target("avx2") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") using namespace std; template ostream& operator<<(ostream& os, const pair& p) { os << '(' << p.first << ',' << p.second << ')'; return os; } template ostream& operator<<(ostream& os, const vector& v) { for (int i = 0 ; i < ssize(v) ; i++) os << v[i] << (i + 1 == ssize(v) ? "" : " "); return os; } /* * */ int main() { // cin.tie(0); // cout.tie(0); // ios::sync_with_stdio(0); // cout << fixed << setprecision(20); #if !defined DEBUG int T; cin >> T; pair P,Q; cin >> P.first >> P.second >> Q.first >> Q.second; auto f = [&](int i) { cout << "? " << i << endl; int x,y; cin >> x >> y; int a = abs(x-P.first)+abs(y-P.second); int b = abs(x-Q.first)+abs(y-Q.second); return a <= b; }; if (P == Q) cout << "! " << 0 << endl; else { int ans = BinarySearch(0,T,f); cout << "! " << ans << endl; } #else mt19937_64 mt{random_device{}()}; for (int testcase = 0 ; ; ) { cerr << "----------" << ++testcase << "----------" << endl; auto a = solve(), b = naive(); if (a != b) { // print testcase cerr << "you: " << a << endl; cout << "correct: " << b << endl; exit(0); } } #endif }