场切了，感觉题有点难评，遂来写题解。
按我场上的思考顺序写。
下文使用 \(x\) 来指代 Sally 的蛋糕。
Subtask 2
注意到 \(1 \le d_i \le 3\) , 并且只有一次询问机会，容易想到需要用三种结果对应三种不同的 \(d_i\) , 具体构造很多，我采用的是加入两个美味度为 \(1\) 的蛋糕，然后询问 \([0,1]\) 与 \([2]\) ，注意因为 \(1 \le d_i\) ，所以我们可以把最美味的蛋糕视为 \(x\) 。
若返回 \(1\) , 则说明 \(d=a_2=1\) 。
若返回 \(0\) , 则说明 \(d=a_2=2\) 。
若返回 \(-1\) , 则说明 \(d=a_2=3\) 。
Subtask 1
考虑扩展 Subtask 2 的做法，可以向 \(a\) 中加入 100 个 \(1\) ，这样 \(x\) 就可视为 \(a_{100}\)，又注意到 \(W=K=100\) ，则可以一次询问排除一个数。
具体来说，对于 \(i \in [1, 100]\) ，我们将 \([0,i-1]\) 中的每个数加入 \(S_1\) ，然后将 \(100\) 加入 \(S_2\) ，若询问返回 \(0\) ，则 \(x=i\) 。
注意到此过程可以通过二分进行优化，但在 Subtesk 2 中不必要。
Subtask 3
注意到 \(K=30\) 且 \(W=10^9\) ，即 \(2^K \approx W\) ，很难不想到与二分或倍增有关，发现 \(N=40\) 略大于 \(30\) ，则自然想到向 \(a\) 中添加 \(2\) 的若干次幂。
此时发现性质：\(a_{i} - 1 = a_0 + a_1 + \cdots + a_{i-1}\) ，即 \(a\) 中前若干个数的和等于下一个数减一。我们可以考虑再向 \(a\) 中加入一个 \(1\) ，这样这个式子就变成了 \(a_{i} = a_0 + a_1 + \cdots + a_{i-1}\) ，对应到询问就是 \(compare\_tastiness([0, 1,\cdot \cdot \cdot ,i-1], [i]) = 0\) 。下面称 \(compare\_tastiness([0, 1,\cdots ,i-1], [i]) = 0\) 为询问 \(i\) 。
考虑加入 \(x\) 后会对询问 \(i\) 产生什么影响，若 \(x\) 的插入位置在 \(a_i\) 之后即 \(x \ge a_i\) (相等视为插在其后，不影响正确性) ，下标 \(i\) 之前的下标不受影响，则该询问返回值仍为 \(0\) 。若 \(x\) 的插入位置在 \(a_i\) 之前即 \(x \le a_i\) ，手玩可以发现询问 \(i\) 返回值一定为 \(1\) 。 于是我们有了一个判断 \(x\) 二进制下最高位 \(1\) 的位置的方法，同时我们也知道了 \(x\) 插入的位置。
实际操作就是从大到小进行判断，先判断 \(x\) 是否大于 \(2^{29}\) ，然后判断 \(x\) 是否大于 \(2^{28}\) ，以此类推，得到第一个 \(1\) 后就停止询问。设 \(2^b \le x < 2^{b+1}\) ，然后将 \(2^b\) 永久加入 \(S_1\) ，将 \(x\) 永久加入 \(S_2\) (此时 \(x\) 的位置为 \(b+1\))。这等效于仅 \(s_2\) 中有值为 \(x-2^b\) 的数，然后可以用 \(2^b\) 以前的数拼出来一个大于等于 1 ，小于等于 \(2^b\) 的数，以此来对 \(x-2^b\) 进行二分查找，最后还原 \(x\) 。
需要注意实现，否则容易超出次数限制。
Subtask 4
发现 \(W\) 的限制缩小到了 2000 ，\(N\) 的限制放大到了 3000 ，但 \(K\) 只为 7 。如果按照二分写，那么询问次数不可能小于10次，所以正解一定不是二分，发现在前面的二分中，我们最多利用两个返回值，能不能同时利用上三种不同的返回值，考虑到 \(3^7\) 略大于 \(W\) ，说明这个想法方向对了。
考虑到 \(N>W\) ，自然想到将 \(1,2,\cdots,2000\) 加入 \(a\) (为了下面叙述方便，也为了下面的一些做法，可以多加入 1 个 \(1\) ，使得下标 0 上的数字为 \(1\) ，其余数字与下标均相等) ，前三个 Subtask 都是先确定了 \(x\) 的位置再求解的，但 Subtask 4 只有 7 次询问机会，并没有多余次数让我们先找到位置再求 \(x\) ，但是因为我们向 \(a\) 中加入的数字是连续的，所以找到 \(x\) 的位置等效于找到 \(x\) 的值。
再思考插入 \(x\) 后的 \(a\) ，里面是包含 \(1\) 到 \(2000\) 的一个从小到大的数列，其中有一个数字出现了两次，问题转化为要找出这个重复的数字。
这个问题看起来很经典，沿用 Subtask 3 的思路，如何在一次询问内判断前 \(i\) 个数有没有重复的数，容易想到对于数列 \([1,2,3,\cdots,i]\) ，\(1+i\)等于两个中位数的和 (如果中位数只有一个，则可以用中位数与中位数-1，然后带上下标 0 上的 \(1\) ) ; 但是若 \(1 \le x<v_1\) ，数列将会变为 \([1,2,3,\cdots,x,x,\cdots,i-1]\) ，发现首项加末项相较原来减少了一，中位数之和较原来减少了二，则\(compare\_tastiness([1,i], [ \left\lfloor \frac{i}{2} \right\rfloor ,\left\lceil \frac{i+1}{2} \right\rceil , (0)])\)返回值会为 \(1\) ，同理可得当 \(v_2 \le x <i\) 时，返回值为 \(-1\)，当 \(x \ge i\) 时，返回值为 \(0\) 。但是有问题，当 \(x=v_1\) 时，返回值也为 \(0\) ,这个做法倒闭了。并且这个做法只能做到 10 次询问。
先考虑解决询问次数问题，我们可以让中间的两个数各向两侧移动相同步数，这样它们的和仍不变，这样整个数列就被分成了三个部分。
我们原来选择将中间两个数放在一个集合里，两侧的数放在一个集合里，我们现在尝试改变，如图，将第一，三个数放入 \(s_1\) , 第二，四个数放入 \(s_2\) 。
但这样初始时 \(s_1\) 的和一定小于 \(s_2\) 的和，难以判断，所以我们可以在初始时向 \(a\) 中加入若干个 2100 与2101，2102，2104等，通过向 \(s_1\) 中加大数，\(s_2\) 中加小数的方法使它们的初始值相同，假设当前 \(x\) 的范围为 \([L,R]\)，分析上图可以发现：
若 \(L \le x < mid_1\)，询问 \((s_1,s_2)\) 的返回值为 \(1\) 。
若 \(mid_1 \le x < mid_2\)，询问 \((s_1,s_2)\) 的返回值为 \(0\) 。
若 \(mid_2 \le x < R+1\)，询问 \((s_1,s_2)\) 的返回值为 \(-1\) 。
于是就做完了，实现三分时需要精细，否则容易多一次询问导致挂 11 分 。