[交互 杂题] Codeforces Gym 100307 NEERC 13 I. Interactive Interception

如果已知起点 我们可以直接二分速度
现在我们都不知道
那么我们每次查询希望把起点和速度组成的二元组尽量平均的分开
这个要一个二分来找询问那个点
然后询问(0,R)就好了

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
typedef long long ll;

const int N=100005;

int V,P;
int l[N],r[N],mid[N];

inline ll f(int t,int c){
  ll ret=0;
  for (int i=0;i<=P;i++){
    if (l[i]>r[i]) continue;
    int mv=c-i;
    if (!t)
      mv=mv>=0?V:-1;
    else
      mv=mv<0?-1:mv/t;
    mid[i]=mv;
    ret+=mv>=r[i]?r[i]-l[i]+1:mv-l[i]+1;
  }
  return ret;
}

int main(){
  string ret;
  freopen("t.in","r",stdin);
  freopen("t.out","w",stdout);
  cin>>P>>V;
  for (int i=0;i<=P;i++) l[i]=0,r[i]=V;
  ll tot=(ll)(V+1)*(P+1);
  for (int t=0;;t++){
    int L=-1,R=P+t*V,MID;
    while (L+1<R)
      if (f(t,MID=(L+R)>>1)*2>=tot)
    R=MID;
      else
    L=MID;
    f(t,R);

    printf("check 0 %d\n",R); fflush(stdout);
    cin>>ret;
    if (ret=="Yes"){
      for (int i=0;i<=P;i++) if (mid[i]<r[i]) r[i]=mid[i];
    }else{
      for (int i=0;i<=P;i++) if (mid[i]+1>l[i]) l[i]=mid[i]+1;
    }

    tot=0;
    for (int i=0;i<=P;i++) if (l[i]<=r[i]) tot+=r[i]-l[i]+1;
    if (tot<=1)
      for (int i=0;i<=P;i++)
        if (l[i]<=r[i]){
      printf("answer %d\n",i+(t+1)*l[i]); fflush(stdout);
      exit(0);
    }
  }
  return 0;
}