インタラクティブな問題.
解法
Binary search と同じで,区間を半分ずつにしていく. 行を 2つの区間に分けたとき,区間の行の個数より駒が少ない区間が存在する. そちらの区間に正解の行がある. 列も同様.
実装
入力と出力を一緒に行う関数を用意すると楽.
使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n; cin >> n;
auto send = [&](ll a, ll b, ll c, ll d) -> ll {
cout << "? " << a << " " << b << " " << c << " " << d << " " << endl;
ll x; cin >> x;
return x;
};
ll h,w;
rep(xi,2){
ll l, r, md;
l = 1, r = n;
rep(i,10){
md = (l+r)/2;
ll x;
if(xi == 0){
x = send(l,md,1,n);
}else{
x = send(1,n,l,md);
}
if(x < md-l + 1){
r = md;
}else{
}
if(r==l) break;
}
h = l;
swap(h,w);
}
cout << "! " << h << " " << w << endl;
return 0;
}