この問題は、チェス盤が 2 次元空間上に存在するため、どのようなクエリを投げるべきかわからず難しく感じられた人もいるかもしれません。
簡単のため、まずは 1 次元の場合を考えてみましょう。すなわち次のような問題です。

数列 \((A_1, A_2, \dots, A_N)\) があります。\(A\) の \(N\) 個の要素のうち \(N-1\) 個は \(1\) で、 \(1\) 個だけ \(0\) が含まれています。次の質問を繰り返して \(A_i = 0\) である \(i\) を特定してください。

• \(P, Q\) を選ぶ。\(A_P, A_{P+1}, \dots, A_{Q}\) の中に \(1\) が何個含まれているかを聞く。

この問題は 二分探索 を利用すれば最大でも \(\lceil \log_2 N \rceil\) 回の質問で答えを出せます。
具体的には、以下に説明する手順を実行すればよいです。

• はじめ、\(L = 1, R = N\) とする。\(L, R\) は、答えが \(\lbrack L, R \rbrack\) の間に含まれていることを意味する変数である。
• \(L \neq R\) の間、次の質問クエリを行う。
  • \(M = \lfloor (L + R) / 2 \rfloor\) とおき、\((P, Q) = (L, M)\) としてクエリを投げる。クエリの答えとして有り得るのは \(M-L+1\) または \(M-L\) で、値に応じて場合分けする。
    • クエリの答えが \(M-L\) の場合、\(\lbrack L, M \rbrack\) の範囲に \(0\) があることがわかるので、\(R \gets M\) に更新する。
    • クエリの答えが \(M-L+1\) の場合、\(\lbrack L, M \rbrack\) の範囲に \(0\) はないことがわかるので、\(L \gets M + 1\) に更新する。

上のアルゴリズムでは調べる区間は 半分ずつになっていくので、\(\lceil \log_2 N \rceil\) 回の質問で答えを求めることができます。

実は、このアルゴリズムを応用すると 2 次元の場合も解くことができます。
問題を分割しましょう。答えとしてあり得るマスは 1 通りしかないので、次の 2 つが分かればこの問題を解くことができます。

• ルークが置かれていないのはどの行か？
• ルークが置かれていないのはどの列か？

この 2 つの情報を別々に求めることを考えます。
まず、クエリの \((C, D)\) を \((1, N)\) に固定したとします。すると、クエリの範囲は \(1\) 列目から \(N\) 列目、すなわち行を固定したときにその行全体となります。 このとき各行のクエリの答えへの寄与は、ルークが置かれてた場合は \(1\), 置かれていない場合は \(0\) です。よって 1 次元の場合の問題と全く同じ状況の問題に帰着することができました。すなわち、\(A, B\) を \(L, R\) とみなして上記のアルゴリズムを適用すると、「ルークが置かれていないのはどの行か？」という問題を \(\lceil \log_2 N \rceil\) 回の質問で求めることができます。また、同様に \((A, B)\) を \((1 ,N)\) に固定すれば「ルークが置かれていないのはどの列か？」という問題を解くことができます。
以上の 2 つの情報を合わせれば、ルークを置くことができるマスを求めることができます。必要な質問の回数は最大でも \(\lceil \log_2 N \rceil \times 2 \leq 10 \times 2 = 20\) 回なので、質問クエリの回数制限にちょうど収まります。計算量も \(\mathrm{O}(\log N)\) 程度で十分余裕があります。よってこの問題を解くことができました。

C++ による実装例は次の通りです。何点か解説します。

• C++ では 出力の末尾に endl をつけると改行とともに flush が行われます。(インタラクティブを C++ で書く場合はこの endl だけ意識すればどうにかなります。)ただし、マクロで endl を "\n" に置き換えている人は flush されない時があるので、自作のテンプレートを使用している人は注意してください。
  • ただし、より厳密な話をすると、実装例のコードは endl を "\n" に置き換えても適切に flush が行われて AC することができます。興味がある人は C++ の仕様について調べてみましょう。
• 4 行目のsend 関数のように、ジャッジプログラムへの出力を引数、ジャッジプログラムから受け取る入力を返り値とする関数を作成すると、cin, cout 周りを書く回数が減って実装がはっきり楽になるのでオススメです。
• 実装例のように二分探索の区間を \([1, N+1)\) のように右半開区間で管理すると、場合分けの実装量が少し減って楽だと思います。(この部分は個人差がありそうです)

#include <iostream>
using namespace std;

int send(int A, int B, int C, int D) {
  cout << "? " << A << " " << B << " " << C << " " << D << endl;
  cin >> A;
  return A;
}

int main() {
  int N;
  cin >> N;
  int U = 1, D = N + 1;
  while (U + 1 != D) {
    int M = (U + D) / 2;
    int c = send(U, M - 1, 1, N);
    (c == M - U ? U : D) = M;
  }
  int L = 1, R = N + 1;
  while (L + 1 != R) {
    int M = (L + R) / 2;
    int c = send(1, N, L, M - 1);
    (c == M - L ? L : R) = M;
  }
  cout << "! " << U << " " << L << endl;
}