#1196462 (C++23) No.2962 Sum Bomb Bomber

• 問題: No.2962 Sum Bomb Bomber
• ユーザー: kwm_t
• 提出日時: 2026-11-01 18:20:00
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 457 ms / 2,000 ms
• コード長: 5,005 bytes
• コンパイル時間: 2,256 ms
• コンパイル使用メモリ: 338,236 KB
• 実行使用メモリ: 9,736 KB
• 平均クエリ数: 191.00
• 最終ジャッジ日時: 2026-11-01 18:20:13
• 合計ジャッジ時間: 9,636 ms
• ジャッジサーバーID （参考情報）: judge7_0 / judge4_0

ファイルパターン	結果
sample	AC * 1
other	AC * 65

ソースコード

#include <bits/stdc++.h>
//#include <atcoder/all>
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<int,int>
template<typename A, typename B> inline bool chmax(A& a, const B& b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> 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 <functional>
#include <utility>

 /**
  * @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 <class T, class F, class Compare = std::less<>>
std::pair<T, decltype(std::declval<F>()(std::declval<T>()))>
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 <class T, class F, class Compare = std::less<>>
std::pair<T, decltype(std::declval<F>()(std::declval<T>()))>
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;
}