CF1028G

题解我就是不交到洛谷上！

交互题普遍难度虚高。

没那么难，就是题目的trick比较新颖，不是很套路。

设当前询问出来的x在 $[l,r]$ 中，则下一次询问应该询问l个数。

考虑交互库给的结果，实际上是这样的：假如我们现在这次询问后还剩q次，则需要让我们把序列划分成一坨区间，这之中每个区间都能在q-1次询问后得出结果。

考虑dp。设f[i][j]为已知x最小可能是i，还剩j次询问时最大可以得出结果的[i,r]长度。用人话说就是最大可求解的r-i+1。转移就随便枚举区间长度转移。

预处理完dp数组之后，直接按照该数组询问即可。

记得用endl。记得用endl。记得用endl。记得用endl。记得用endl。记得用endl。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=10000;
ll f[N+5][6];
inline void solve(ll i,ll l,ll r){
    ll p=l+f[min(l,N)][i-1]-1,k=min(l,N);
    vector<ll> v;
    for(int j=1;j<=k;++j){
        ++p;v.push_back(p);
        p+=f[min(p+1,N)][i-1];
    }
    cout<<k<<endl;
    for(ll i:v)cout<<i<<" ";
    cout<<endl;
    ll x;cin>>x;
    if(x==-1)exit(0);
    if(!x){solve(i-1,l,v[0]-1);return;}
    if(x==k){solve(i-1,v[k-1]+1,r);return;}
    solve(i-1,v[x-1]+1,v[x]-1);
}
int main(){
    for(int i=1;i<=N;++i)f[i][1]=i;
    for(int j=2;j<=5;++j){
        for(int i=1;i<=N;++i){
            ll r=i+f[i][j-1]-1;
            for(int k=1;k<=i;++k){
                if(r>=N){r+=(i-k+1)*(f[N][j-1]+1);break;}
                r+=f[r+2][j-1]+1;
            }
            f[i][j]=r-i+1;
        }
    }
    solve(5,1,f[5][1]);
    return 0;
}