自动搬运

查看原文

来自洛谷，原作者为

	FFTotoro 龙猫

搬运于2025-08-24 23:08:48，当前版本为作者最后更新于2025-01-26 18:19:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

给 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;
}