#include //#include using namespace std; //using namespace atcoder; //using mint = modint1000000007; //const int mod = 1000000007; //using mint = modint998244353; //const int mod = 998244353; //const int INF = 1e9; //const long long LINF = 1e18; #define rep(i, n) for (int i = 0; i < (n); ++i) #define rep2(i,l,r)for(int i=(l);i<(r);++i) #define rrep(i, n) for (int i = (n) - 1; i >= 0; --i) #define rrep2(i,l,r)for(int i=(r) - 1;i>=(l);--i) #define all(x) (x).begin(),(x).end() #define allR(x) (x).rbegin(),(x).rend() #define P pair template inline bool chmax(A& a, const B& b) { if (a < b) { a = b; return true; } return false; } template inline bool chmin(A& a, const B& b) { if (a > b) { a = b; return true; } return false; } /** * @file ternarysearch.hpp * @brief 三分探索 * @author kwm_t * @see https://github.com/kwm-t/cp-library/blob/main/algorithm/search/ternarysearch.hpp */ #ifndef KWM_T_ALGORITHM_SEARCH_TERNARY_SEARCH_HPP #define KWM_T_ALGORITHM_SEARCH_TERNARY_SEARCH_HPP #include #include /** * @brief 三分探索 (整数) * * @details * 単峰関数 (unimodal function) に対して最小値または最大値を探索する。 * Compare により最小値 / 最大値のどちらも求めることができる。 * * Typical Use: * 凸関数 / 凹関数の最小値・最大値探索 * * Complexity: * Time: O(log(r-l)) + O(1) * * Template Parameters: * T : 整数型 (int / long long など) * F : 評価関数 f(T) * Compare : 比較関数 (std::less / std::greater) * * Parameters: * l : 探索区間左端 * r : 探索区間右端 * f : 評価関数 * comp : 比較関数 * * Return: * {最適な位置, その値} * * Requirements: * f は単峰関数であること * * Notes: * 区間が小さくなった後は全探索する * * Example: * ```cpp * auto f = [&](long long x){ * return (x - 10) * (x - 10); * }; * * // 最小値 * auto res = ternary_search(0LL, 100LL, f); * * // 最大値 * auto res2 = ternary_search(0LL, 100LL, f, std::greater<>()); * ``` * * Verified: * https://atcoder.jp/contests/awc0115/submissions/77544766 */ namespace kwm_t::algorithm::search { template > std::pair()(std::declval()))> ternary_search(T l, T r, F f, Compare comp = Compare()) { using U = decltype(f(l)); while (r - l > 2) { T ml = l + (r - l) / 3; T mr = r - (r - l) / 3; if (comp(f(ml), f(mr))) r = mr; else l = ml; } T best = l; U val = f(l); for (T i = l + 1; i <= r; ++i) { U v = f(i); if (comp(v, val)) { best = i; val = v; } } return std::pair{ best, val }; } } // namespace kwm_t::algorithm::search /** * @brief 三分探索 (実数) * * @details * 実数区間に対する三分探索。 * counter 回反復することで近似解を求める。 * * Typical Use: * 実数値の最小値 / 最大値探索 * * Complexity: * Time: O(counter) * * Template Parameters: * T : 浮動小数点型 (double / long double) * F : 評価関数 f(T) * Compare : 比較関数 * * Parameters: * l : 探索区間左端 * r : 探索区間右端 * f : 評価関数 * counter : 反復回数 * comp : 比較関数 * * Return: * {近似位置, その値} * * Requirements: * f は単峰関数であること * * Example: * ```cpp * auto f = [&](double x){ * return (x - 3.14) * (x - 3.14); * }; * * auto res = ternary_search_double(0.0, 10.0, f); * ``` * * Verified: * */ namespace kwm_t::algorithm::search { template > std::pair()(std::declval()))> ternary_search_double(T l, T r, F f, int counter = 100, Compare comp = Compare()) { using U = decltype(f(l)); while (counter--) { T ml = l + (r - l) / 3; T mr = r - (r - l) / 3; if (comp(f(ml), f(mr))) r = mr; else l = ml; } return std::pair{ l, f(l) }; } } // namespace kwm_t::algorithm::search #endif // KWM_T_ALGORITHM_SEARCH_TERNARY_SEARCH_HPP long long local(int x, int y) { int tx = 0, ty = -1; return abs(tx - x) + abs(ty - y); } auto query(int x, int y) { std::cout << 1 << " " << x << " " << y; std::cout << std::endl; fflush(stdout); // return local(x, y); long long get; std::cin >> get; return get; } auto answer(int x, int y) { std::cout << 2 << " " << x << " " << y; std::cout << std::endl; fflush(stdout); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; auto f = [&](int x)->long long { return query(x, 0); }; auto [x, xv] = kwm_t::algorithm::search::ternary_search(-100000008, 100000008, f); auto g = [&](int y)->long long { return query(0, y); }; auto [y, yv] = kwm_t::algorithm::search::ternary_search(-100000008, 100000008, g); answer(x, y); return 0; }