713B - Searching Rectangles - CodeForces Solution

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 400005
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
using namespace std;
int n;
struct rec { int x1,y1,x2,y2; } rec1={ 1,1,2,4 },rec2={ 1,5,2,5 };
bool in(int x1,int y1,int x2,int y2,rec a)
{
    return x1<=a.x1 && a.x2<=x2 && y1<=a.y1 && a.y2<=y2;
}
int ask(int x1,int y1,int x2,int y2)
{
    cout<<"? "<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<'\n';
   // return in(x1,y1,x2,y2,rec1)+in(x1,y1,x2,y2,rec2);
    int k;
    cin>>k;
    return k;
}
pair <rec,rec> Findrange()
{
    int l=1,r=n;
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(ask(1,1,n,mid)>0) r=mid; else l=mid+1;
    }
    if(l<n && ask(1,l+1,n,n)>0) return { { 1,1,n,l },{ 1,l+1,n,n } };
    l=1,r=n;
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(ask(1,1,mid,n)>0) r=mid; else l=mid+1;
    }
    return { { 1,1,l,n },{ l+1,1,n,n } };
}
rec Findrec(rec a)
{
    int l=a.y1,r=a.y2,x1,y1,x2,y2;
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(ask(a.x1,a.y1,a.x2,mid)>0) r=mid; else l=mid+1;
    }
    y2=l;

    l=a.y1,r=a.y2;
    while(l<r)
    {
        int mid=(l+r+1)>>1;
        if(ask(a.x1,mid,a.x2,a.y2)>0) l=mid; else r=mid-1;
    }
    y1=l;

    l=a.x1,r=a.x2;
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(ask(a.x1,a.y1,mid,a.y2)>0) r=mid; else l=mid+1;
    }
    x2=l;

    l=a.x1,r=a.x2;
    while(l<r)
    {
        int mid=(l+r+1)>>1;
        if(ask(mid,a.y1,a.x2,a.y2)>0) l=mid; else r=mid-1;
    }
    x1=l;
    return { x1,y1,x2,y2 };
}
int main()
{
 //   freopen("ntu.inp","r",stdin);
   // freopen("ntu.out","w",stdout);
    cin>>n;
    pair <rec,rec> Range=Findrange();
    rec u=Findrec(Range.fst),v=Findrec(Range.snd);
    cout<<"! "<<u.x1<<" "<<u.y1<<" "<<u.x2<<" "<<u.y2<<" "<<v.x1<<" "<<v.y1<<" "<<v.x2<<" "<<v.y2;
}