题目

CF1153E Serval and Snake

很有意思的一道交互题

做法

我们观察到，每次查询一行，当这一行仅包含一端是返回的答案是奇数

根据这个性质查询每一行每一列，我们大体能知道两端的位置

查询矩阵时也是这个道理(奇数)，可以二分行和列从而得出答案

Code

#include<bits/stdc++.h>

typedef int LL;

LL n;

LL fir_1,fir_2,sec_1,sec_2;

inline LL Check(LL x,LL y,LL _x,LL _y){

	LL val;

	printf("? %d %d %d %d\n",x,y,_x,_y);

	fflush(stdout);

	scanf("%d",&val);

	return val;

}

int main(){

	std::cin>>n;

	for(LL i=1;i<n;++i){

		LL val(Check(i,1,i,n));

		if(val&1){

			if(fir_1) sec_1=i;

			else fir_1=i;

		}

	}

	if(!sec_1 && fir_1) sec_1=n;

	for(LL i=1;i<n;++i){

		LL val(Check(1,i,n,i));

		if(val&1){

			if(fir_2) sec_2=i;

			else fir_2=i;

		}

	}

	if(!sec_2 && fir_2) sec_2=n;

    if(fir_1 && fir_2){

    	LL l=1,r=n;

    	while(l!=r){

    		LL mid(l+r>>1);

    		if(Check(fir_1,l,fir_1,mid)&1) r=mid;

    		else l=mid+1;

		}

		LL ret(l);

		if(ret==fir_2){

			printf("! %d %d %d %d\n",fir_1,ret,sec_1,sec_2);

		}else{

			printf("! %d %d %d %d\n",fir_1,ret,sec_1,fir_2);

		}

	}else{

		if(fir_1){

			LL l=1,r=n;

    	    while(l!=r){

    		    LL mid(l+r>>1);

    		    if(Check(fir_1,l,fir_1,mid)&1) r=mid;

    		    else l=mid+1;

		    }

		    LL ret(l);

		    printf("! %d %d %d %d\n",fir_1,ret,sec_1,ret);

		}else{

			LL l=1,r=n;

    	    while(l!=r){

    		    LL mid(l+r>>1);

    		    if(Check(l,fir_2,mid,fir_2)&1) r=mid;

    		    else l=mid+1;

		    }

			LL ret(l);

		    printf("! %d %d %d %d\n",ret,fir_2,ret,sec_2);

		}

	}

	return 0;

}