[PA2016] 寻踪 / Ciepło-zimno 题解

· · 题解

给 mashup 验了个题，简单来写一个题解。

在交互过程中，考虑缩小每一维的取值范围，不妨认为第 i 维 p_i 的取值范围为 [l_i,r_i]。

令每一维的值域为 [0,R]。一开始我们没有任何信息，所以 l_i=0,r_i=R。

考虑每次取出 r_i-l_i+1 最大的 i，构造两个向量 V_1,V_2 满足 V_{1,i}=l_i,V_{2,i}=r_i 且 \forall j\ne i,V_{1,j}=V_{2,j}=\left\lfloor\frac{l_j+r_j}{2}\right\rfloor 进行比较（令其他 V_{1,j}(j\ne i) 和 V_{2,j}(j\ne i) 的值为 l_j 与 r_j 的中点，可以尽量减少其他维度的值影响到答案）。

这样的思路类似二分，可以近似地得出 p_i 离 l_i 还是 r_i 更近——为什么说是“近似地”？因为对于 r_i-l_i+1 为偶数的情况，假设存在若干个 r_j-l_j=r_i-l_i 的 j(j\ne i)，那么按上面的方式询问，答案要对 \left\lceil\frac{r_i-l_i+1}{2}\right\rceil 取 \max，最坏情况下只能把值域缩小到 \left[l_i,\left\lfloor\frac{l_i+r_i}{2}\right\rfloor+1\right]。

但这种方法已经足够将最终所有的 l_i 和 r_i 缩小到满足 r_i-l_i\le 1。此时对于所有 r_i-l_i=1 的 i 单独处理：如果 l_i>0，那么构造向量 V_1,V_2 满足 V_{1,i}=l_i-1,V_{2,i}=r_i 且 V_{1,j}=V_{2,j}=l_j(j\ne i) 进行比较，就可以得出 p_i=l_i 还是 r_i；由于 R\ge 2，所以对于 l_i=0 的情况同理。

询问次数是 O(n\log R) 的。

放代码：

#include<bits/stdc++.h>
using namespace std;
struct info{
  int p,l,r;
  info(int p=0,int l=0,int r=0):p(p),l(l),r(r){}
  inline bool operator <(const info &x)const{
    return r-l<x.r-x.l;
  }
};
int main(){
  ios::sync_with_stdio(false);
  int n,k,v; cin>>n>>k>>v;
  vector<pair<int,int> > w(n,make_pair(0,v));
  priority_queue<info> q;
  for(int i=0;i<n;i++)
    q.emplace(i,0,v);
  while(q.top().r-q.top().l>1){
    auto [p,l,r]=q.top(); q.pop();
    cout<<"? ";
    for(int i=0;i<n;i++){
      if(i==p)cout<<l<<' ';
      else cout<<(w[i].first+w[i].second>>1)<<' ';
    }
    cout<<endl;
    int x; cin>>x;
    cout<<"? ";
    for(int i=0;i<n;i++){
      if(i==p)cout<<r<<' ';
      else cout<<(w[i].first+w[i].second>>1)<<' ';
    }
    cout<<endl;
    if(cin>>x;x)w[p].first=(l+r>>1)+1;
    else{
      if(r-l+1&1)w[p].second=l+r>>1;
      else w[p].second=(l+r>>1)+1;
    }
    q.emplace(p,w[p].first,w[p].second);
  } // 每次取出 r[i]-l[i] 最大的 i 进行询问
  for(int i=0;i<n;i++)
    if(w[i].first<w[i].second){
      if(w[i].second==v){
        cout<<"? ";
        for(int j=0;j<n;j++){
          if(i==j)cout<<w[j].first-1<<' ';
          else cout<<w[j].first<<' ';
        }
        cout<<endl;
        int x; cin>>x;
        cout<<"? ";
        for(int j=0;j<n;j++){
          if(i==j)cout<<w[j].second<<' ';
          else cout<<w[j].first<<' ';
        }
        cout<<endl;
        if(cin>>x;x)w[i].first=w[i].second;
        else w[i].second=w[i].first;
      }
      else{
        cout<<"? ";
        for(int j=0;j<n;j++){
          if(i==j)cout<<w[j].second+1<<' ';
          else cout<<w[j].first<<' ';
        }
        cout<<endl;
        int x; cin>>x;
        cout<<"? ";
        for(int j=0;j<n;j++){
          if(i==j)cout<<w[j].first<<' ';
          else cout<<w[j].first<<' ';
        }
        cout<<endl;
        if(cin>>x;x)w[i].second=w[i].first;
        else w[i].first=w[i].second;
      }
    } // 特殊处理 r[i]-l[i]=1 的 i
  cout<<"! ";
  for(auto i:w)cout<<i.first<<' ';
  cout<<endl;
  return 0;
}