题解：CF1153E Serval and Snake

jess1ca1o0g3 · 2025-09-21 21:39:27 · 题解

首先非常困难的一点就是要注意到当回答为奇数时，说明有恰好一个端点（头尾）在矩形里。

感性理解一下，没有端点就是在中间，肯定是从外面进来再出去，几个进来出去肯定就是偶数。要不然就是头尾都在，就少一个进来出去。

考虑枚举行，找到为奇数的两行。现在横坐标确定了，直接在行上二分就行。要不然头尾都在一行，再枚举列，然后二分。这样最多的询问次数是 n+n+2\log n=2020，刚好倒闭。

然后你发现在枚举列的时候，第二列是不用二分的，因为横坐标一定相同。这下就过了。

代码：

#include<bits/stdc++.h>
#define i64 long long
#define L(a,b,c,d) for(int a=b;a<=c;a+=d)
#define R(a,b,c,d) for(int a=b;a>=c;a-=d)

using namespace std;
const int N=1e5+5;

void solve();
int n,p;
pair<int,int> a[3];

signed main(){
  int Test=1;
//  scanf("%d",&Test);
  while(Test--) solve();
  return 0;
}

int query(int x1,int y1,int x2,int y2){
  int s;
  cout<<"? "<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<endl;
  cin>>s;
  return s;
}

int bs1(int k){
  int l=0,r=n+1,m;
  while(l+1<r){
    m=(l+r)>>1;
    if(query(k,l+1,k,m)&1) r=m;
    else l=m;
  }
  return r;
}

int bs2(int k){
  int l=0,r=n+1,m;
  while(l+1<r){
    m=(l+r)>>1;
    if(query(l+1,k,m,k)&1) r=m;
    else l=m;
  }
  return r;
}

void solve(){
  cin>>n;
  L(i,1,n,1){
    int s=query(i,1,i,n);
    if(s&1) a[++p]={i,bs1(i)};
  }
  if(!p){
    L(i,1,n,1){
      int s=query(1,i,n,i);
      if(s&1){
        if(!p) a[++p]={bs2(i),i};
        else a[++p]={a[1].first,i};
      }
    }
  }
  cout<<"! "<<a[1].first<<" "<<a[1].second<<" "<<a[2].first<<" "<<a[2].second<<endl;
}