【题解】CF1039B

Link

一道挺有意思的交互

看自己的代码评测的时候有一种看着自己的孩子的感觉（？

发现值域很大但是这个点每次变化的幅度很小（$k \le 10$）于是想到二分这个点所在的区间，缩小到一定范围之后在这个区间内随机询问位置。

区间大小理论最小值应该是 $4k$ ，你可以取 $5k$ 或者 $6k$ 或者直接取 $50 / 60$，$k$ 很小所以无论怎么搞都无所谓（

我的代码也许有不必要的特判（

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n,k;
string s;
int query(int l,int r){
	cout<<l<<' '<<r<<endl;
	cin>>s;
	if (s=="Yes") return 1;
	else return 0;
}

signed main()

{
	random_device rd;
	cin>>n>>k;
	if (n==1){
		cout<<"1 1"<<endl;
		return 0;
	}

	int l=1,r=n;
	while (1){
		l=max(1ll,l-k*2);r=min(n,r+k*2);//这里理论上不需要 k*2 只需要 k，但是这样会导致区间调整的太慢
		int mid=l+r>>1;
		int tmp=query(l,mid);
		if (tmp==1) r=mid;
		else l=mid+1;

		if (l==r && k==0){
			cout<<l<<" "<<l<<endl;
			cin>>s;
			return 0;
		}

		if (l+6*k>=r){
			tmp=rd()%(r-l+1)+l;	
			int res=query(tmp,tmp);
			if (res==1) return 0;
		}
	}
	return 0;
}