交互题好玩！

看到各测试点限制各不相同，考虑数据点分治。

约定记号

• \(f(S)=\sum_{i\in S}a_i\)。

形式化题意

你需要猜出评测机里一个 \([1,W]\) 中的正整数 \(d\)。为此你需要构造一个长度 \(\le N\)，值域 \([1,W+200]\) 的正整数序列。评测机会把该序列排序并把需要猜的数插入到正确位置。

设排序后序列为 \(\{a_i\}_{i=0}^m\)。接下来你最多可以询问 \(K\) 次。每次询问需要给出两个下标集合 \(S_1,S_2\)，满足 \(S_1\cap S_2=\varnothing\) 且 \(S_1,S_2\subseteq \{0,1,\dots,m\}\)。评测机会返回 \(f(S_1)\) 和 \(f(S_2)\) 的大小关系。请猜出评测机中的数。

Subtask1

传 \((1,2,3,\dots,W)\)。暴力枚举到第一个满足 \(a_i=a_{i+1}\) 的位置，则必有 \(d=i+1\)。

Subtask2

传序列 \((1,2,3)\)。插入 \(d\) 排序后，必然有 \(a_0=1, a_3=3\)。我们只需比较 \(a_0+a_3=4\) 与 \(a_1+a_2\) 的大小。具体地：

• 若 \(d=1\)：\(\{a\}=(1,1,2,3)\)，\(a_0+a_3>a_1+a_2\)
• 若 \(d=2\)：\(\{a\}=(1,2,2,3)\)，\(a_0+a_3=a_1+a_2\)
• 若 \(d=3\)：\(\{a\}=(1,2,3,3)\)，\(a_0+a_3<a_1+a_2\)

Subtask3

注意到 \(K=\lceil\log_2 W\rceil\)，考虑二进制拆分，一次询问确定一位。

我们传 \((1,2,2^2,2^3,\dots,2^{29})\)。该序列满足 \(\sum_{k=0}^{i-1}a_k<a_i\) 的性质。观潮到插入 \(d\) 之后，在 \(d\) 及其右侧该性质会被破坏。

那么我们从右往左找到最大的满足以上性质的 \(i\)。那么 \(d\) 的第 \(i\) 位一定是 \(1\)。然后依次尝试加上 \(2^{i-1},2^{i-2},\dots,1\) 即可确定剩余位。恰好询问 \(30\) 次。

Subtask4

如果直接套用 Subtask 3 的做法可以获得 \(11\) 分。由于 \(2^K<W\)，该做法没有前途。

注意到 \(K=\lceil\log_3 W\rceil\)，而 \(3^7=2187<W+200\)。这强烈暗示我们采用三分做法，需要一次询问将搜索范围缩小至 \(1/3\)。

发现 \(N\) 的限制非常宽松。构造序列 \((1,2,3,\dots,3^7)\)。注意到，该序列满足性质 \(a_i+a_j=a_{i+k}+a_{j-k}\)。

维护 \(d\) 所在的下标区间 \([l,r]\)，初始时 \(l=0,r=2187\)。

每次取区间三等分点 \(m_1=l+(r-l)/3,m_2=r-(r-l)/3\)，查询 \(S_1=\{m_1,m_2\},S_2=\{l,r\}\)。

1. \(f(S_1)<f(S_2)\)：\(d\) 插在 \([l,m_1]\) 段中。
2. \(f(S_1)=f(S_2)\)：原性质仍然成立，\(d\) 插在 \([m_1,m_2]\) 段中。
3. \(f(S_1)>f(S_2)\)：\(d\) 插在 \([m_2,r]\) 段中。

然后不断三分即可，注意边界和细节问题。

Code

#include "cake.h"
#include <vector>
#include <numeric>
#define rep(i,a,b) for(int i(a);i<b;++i)
#define per(i,a,b) for(int i(a);i>b;--i)
#define rept(i,a,b) for(int i(a);i<=b;++i)
#define pert(i,a,b) for(int i(a);i>=b;--i)
#define eb emplace_back
using namespace std;
vector<int> bake_cakes(int N,int W,int K){
    if(K==1) return {1,2,3};
    if(K==100){
        vector<int> res(100);
        iota(res.begin(),res.end(),1);
        return res;
    }
    if(K==30){
        vector<int> res(30);
        rep(i,0,30) res[i]=1<<i;
        return res;
    }
    vector<int> res;
    rept(i,1,2187) res.eb(i);
    return res;
}
int find_tastiness(int m,int W,int K){
    if(K==1){
        int k=compare_tastiness({0,3},{1,2});
        return k==-1?3:(k?1:2);
    }
    if(K==100){
        rept(i,0,99){
            if(!compare_tastiness({i},{i+1})) return i+1;
        }
        return 0;
    }
    if(K==30){
        int ans=0,h=-1;
        pert(i,29,1){
            vector<int> t(i);
            iota(t.begin(),t.end(),0);
            if(compare_tastiness(t,{i})==-1){
                h=i;
                break;
            }
        }
        if(h==-1) return 1;
        ans|=1<<h;
        pert(i,h-1,0){
            vector<int> t;
            rep(i,0,30) if(ans>>i&1) t.eb(i);
            t.eb(i);
            int k=compare_tastiness(t,{h+1});
            if(!k) return ans|1<<i;
            if(k==-1) ans|=1<<i;
        }
        return ans;
    }
    int l=0,r=2187,cur=729;
    while(l+1<r){
        int k=compare_tastiness({l+cur,r-cur},{l,r});
        if(k==-1) r=l+cur;
        else if(!k) l+=cur,r-=cur;
        else l=r-cur;
        cur/=3;
    }
    return r;
}