首页 > 代码库 > CF 714D Searching Rectangles 交互题 二分
CF 714D Searching Rectangles 交互题 二分
题意:交互题,已知一个n*n的地图,电脑藏了两个不相交的矩形(矩形的边和坐标轴平行).
每次向电脑询问左下[x1,y1]右上[x2,y2]的矩形内完全包含多少个藏着的矩形.
n<=2^16.请在200次内猜出两个矩形左下,右上坐标.
先二分出两个不相交矩形的分界线,要么横着要么竖着.
接在在每一快中二分出矩形的四条边即可(最左,右,上,下边界)
#include <bits/stdc++.h> using namespace std; int n,ans[20],cnt=0; inline int out(int x,int y,int fx,int fy) { if(x>fx||y>fy)return 0; printf("? %d %d %d %d\n",x,y,fx,fy); fflush(stdout); int num; cin>>num; return num; } inline void solve(int x,int y,int fx,int fy) { int l=x,r=fx,Ans=x; while(l<=r) { int mid=(l+r)>>1; int f=out(mid,y,fx,fy); if(f) l=mid+1,Ans=mid; else r=mid-1; } ans[++cnt]=Ans; l=y,r=fy,Ans=y; while(l<=r) { int mid=(l+r)>>1; int f=out(x,mid,fx,fy); if(f==0)r=mid-1; else l=mid+1,Ans=mid; } ans[++cnt]=Ans; l=x,r=fx,Ans=fx; while(l<=r) { int mid=(l+r)>>1; int f=out(x,y,mid,fy); if(f==0)l=mid+1; else r=mid-1,Ans=mid; } ans[++cnt]=Ans; l=y,r=fy,Ans=fy; while(l<=r) { int mid=(l+r)>>1; int f=out(x,y,fx,mid); if(f==0)l=mid+1; else r=mid-1,Ans=mid; } ans[++cnt]=Ans; } int main() { cin>>n; int l=1,r=n,flag=0; while(l<=r) { int mid=(l+r)>>1; int f=out(1,1,n,mid),g=out(1,mid+1,n,n); if(f&&g)flag=1; if(f==0)l=mid+1; else r=mid-1; } if(flag) { solve(1,1,n,l); solve(1,l+1,n,n); } else { l=1,r=n; while(l<=r) { int mid=(l+r)>>1; int f=out(1,1,mid,n); if(f==0)l=mid+1; else r=mid-1; } solve(1,1,l,n); solve(l+1,1,n,n); } printf("! "); for(int i=1;i<=8;i++)printf("%d ",ans[i]); printf("\n"); return 0; }
CF 714D Searching Rectangles 交互题 二分
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。