### 問題 [AtCoder Beginner Contest 269 E問題](https://atcoder.jp/contests/abc269/tasks/abc269_e) ### アプローチ上下それぞれ10回までなら質問が出来るので、二分探索で左の境界から真ん中までのルークの数を聞き、その数が探索区間と同じ長さならそこには候補地はない為、左の境界を真ん中に移す、そうでなければ右の境界を真ん中にうつし、返ってきた数が0のときこそがまさしく求めたい行/列であると考える。 ### 該当コード ```C++ #include #include #include using namespace std; #define ll long long void solve() { ll N; cin >> N; ll left = 1; ll right = N; ll y; while (true) { ll mid = (left + right) / 2; cout << "?" << " " << 1 << " " << N << " " << left << " " << mid << endl; ll T; cin >> T; if (T == 0) { y = mid; break; } else if (T == mid - left + 1) { left = mid + 1; } else { right = mid; } } ll top = 1; ll bottom = N; ll x; while (true) { ll mid2 = (top + bottom) / 2; cout << "?" << " " << top << " " << mid2 << " " << 1 << " " << N << endl; ll T; cin >> T; if (T == 0) { x = mid2; break; } else if (T == mid2 - top + 1) { top = mid2 + 1; } else { bottom = mid2; } } cout << "!" << " " << x << " " << y << endl; } int main() { solve(); } ``` # 質問上のコードを通そうとすると、大型のケースでは「正解」でかつ「不正解」は出力されないものの、10個ほどのケースで時間切れを起こします。個人的には左右の境界の設定の仕方かwhileループの抜け出し方に問題があるとは疑っているのですが、具体的にどのような例においてループから抜けられないのかがわからずにいます。どこかお力添え頂ける箇所がございましたら、ご教授のほどよろしくお願い申し上げます。

	@@ -1,1 +1,1 @@
1	- 二分探索が無限ループになる
1	+ 二分探索の無限ループから抜け出せない

質問編集履歴