Codeforces Round #551 (Div. 2)

好久没写 interactive题了,这题真是折磨了我好久啊,题目比较简单,就是在2019次query内给出snake的首尾坐标,考虑到一般情况下首尾所在的行列度数为odd ,暴力处理一维,另一维二分就好了

但是这样并不能ac,这里少考虑了首尾在同行或同列的情况,对于这种情况再次暴力处理另一维,然后二分另一维坐标就好了

query次数易得至多为1998+2*log(1000)<2019

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=3e5+5;
int rsc(int x,int n)
{
    int l=1,r=n;
    while(l<r)
    {
        int mid=(l+r)>>1;
        printf("? %d %d %d %d\n",x,l,x,mid);
        fflush(stdout);
        int res;
        scanf("%d",&res);
        if(res&1) r=mid;
        else l=mid+1;
    }
    return l;
}
int csc(int x,int n)
{
    int u=1,d=n;
    while(u<d)
    {
        int mid=(u+d)>>1;
        printf("? %d %d %d %d\n",u,x,mid,x);
        fflush(stdout);
        int res;
        scanf("%d",&res);
        if(res&1) d=mid;
        else u=mid+1;
    }
    return u;
}
int main()
{
    int n;
    scanf("%d",&n);
    vector<int> v;
    for(int i=1; i<=n; i++)
    {
        printf("? %d 1 %d %d\n",i,i,n);
        fflush(stdout);
        int x;
        scanf("%d",&x);
        if(x&1) v.push_back(i);
    }
    if(!v.empty())
    {
        vector<int> c;
        for(int i=1;i<=n;i++)
        {
            printf("? 1 %d %d %d\n",i,n,i);
            fflush(stdout);
            int x;
            scanf("%d",&x);
            if(x&1) c.push_back(i);
        }
        if(!c.empty())
        {
            printf("? %d %d %d %d\n",v[0],c[0],v[0],c[0]);
            fflush(stdout);
            int x;
            scanf("%d",&x);
            if(x&1) return printf("! %d %d %d %d\n",v[0],c[0],v[1],c[1])*0;
            else return printf("! %d %d %d %d\n",v[0],c[1],v[1],c[0])*0;
        }
        int  c1=rsc(v[0],n);
        int r1=v[0],r2=v[1];
        printf("! %d %d %d %d\n",r1,c1,r2,c1);
        fflush(stdout);
    }
    else
    {
        vector<int> c;
        for(int i=1; i<=n; i++)
        {
            printf("? 1 %d %d %d\n",i,n,i);
            fflush(stdout);
            int x;
            scanf("%d",&x);
            if(x&1) c.push_back(i);
        }
        int c1=c[0],c2=c[1];
        int r1=csc(c1,n);
        printf("! %d %d %d %d\n",r1,c1,r1,c2);
        fflush(stdout);
    }
}