ABC 269 E - Last Rook（交互题）

https://atcoder.jp/contests/abc269/tasks/abc269_e

有一个N*N的棋盘和N辆车。
现在，n-1辆车被放在棋盘上，你必须放置1辆车，满足以下所有条件。

没有一行包含两个或更多的车。
没有一列包含两个或更多的车。
你将选择一个未被车占据的方块，并将车放在该方块上。(可以证明，在这些条件下，至少有一个方块可以放置车。)
然而，你不能直接看到棋盘上的哪些方格被车占据。
相反，你可以通过以下方式向法官提出最多20个问题。
你选择整数A，B，C，D使得1≤A≤B≤N，1≤C≤D≤N，求正方形(i，j)形成的矩形区域内的车数使得A≤i≤B，C≤j≤D。
找到一个格子放置车。

这是一个交互式任务(你的程序通过输入和输出与法官的程序交互)。 
首先，从标准输入接收棋盘的大小N。
接下来，重复问一个问题，直到你找到放置车的方块。 问题应该以下列格式打印到标准输出:? A B C D
标准输入将以下列格式给出响应:
在这里，T是问题的答案，或者如果问题无效或者已经问了超过20个问题，则为-1。当法官返回-1时，该提交已被视为不正确。在这种情况下，立即终止程序。
当你找到一个放置车的正方形时，设(X，Y)是那个正方形(单独的一个格子)，并按以下格式打印一个答案：! X Y。然后，立即终止程序。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    //先输入一个n，正方形的大小
	int n;
	cin>>n;
	int x,y;//查找行和列（x行y列）
	int l=1,r=n;
	while(l<=r)
    {
		int mid=(l+r)/2;
		printf("? 1 %d 1 %d\n",mid,n);
		fflush(stdout);
		int flag;
		cin>>flag;
		if(flag==-1) return 0;
		if(flag<mid)
		{
			r=mid-1;
            x=mid;//行
		}
		else l=mid+1;
	}
	l=1,r=n;
	while(l<=r)
    {
		int mid=(l+r)/2;
		printf("? 1 %d 1 %d\n",n,mid);
		fflush(stdout);
		int flag;
		cin>>flag;
		if(flag==-1) return 0;
		if(flag<mid)
		{
			r=mid-1;
            y=mid;//列
		}
		else l=mid+1;
	}
	printf("! %d %d\n",x,y);
	fflush(stdout);
	return 0;
}