题目
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;
}