交互、位运算、贪心

目标是最小化询问次数，考虑逐位确定有问题的果汁编号。为了方便位运算把编号从 $1 \sim n$ 调整到 $0 \sim n-1$ 后处理。

首先对于 $n$ 给出询问次数 $\lfloor \log_{2} (n-1) \rfloor + 1$，因为如果 $n=2^k$ 那么 $n$ 的二进制最高位是不需要询问的。

然后逐位询问，第 $i$ 次询问二进制下编号第 $i$ 位为 $1$ 的所有果汁中是否存在变质果汁，这样最终返回的字符串就是答案的二进制表示，把答案调整回 $1 \sim n$ 的范围之后输出。注意由于低位先被询问，应当翻转给出的字符串之后再用 bitset 获取答案。

#include<bits/stdc++.h>
using namespace std;
int n,ans;
string s;
int main(){
    ios::sync_with_stdio(0);
    cin>>n,--n,ans=log2(n)+1;
    cout<<ans<<endl;
    for(int i=1;i<=ans;i++){
        vector<int> v;
        for(int j=0;j<=n;j++) if((j>>(i-1))&1) v.push_back(j+1);
        cout<<v.size();
        for(int j:v) cout<<' '<<j;
        cout<<endl;
    }
    cin>>s,reverse(s.begin(),s.end());
    cout<<bitset<64>(s).to_ullong()+1<<endl;
    return 0;
}