[WC2019] I 君的商店

首先考虑，若我们知道一个数，我们如何知道其他数是1还是0

假设已知 \(a\) ，对于 \(b\leq c\) 可知：

若 \(a\leq b+c\) 则有 \(a\leq c\) （否则 \(a=0,c=1\) 不满足条件）

若 \(a\geq b+c\) 则有 \(b=0\) （否则 \(b+c=2\) ）

现在我们考虑如何知道一个数。显然，虽然相同时返回的结果很随机，但 \(1\) 一定比 \(0\) 大于更多的数。

也就是说，通过 \(2n\) 次比较，可知一个 \(1\) 的位置。

然后将这个 \(1\) 与其他位置比较即可。（最后一个数无法成对，但通过奇偶性可知）

这样次数是 \(2n+5n=7n\) 无法通过。

考虑优化 \(5n\) 不太可行。于是着手 \(2n\) 。可否不找出最大值呢？

发现上述条件中有些没有用到，因为 \(a\) 一直都是1 。如果 \(a\) 不一定是1 ，我们考虑上述第二条是可以直接求出 \(b\) 的，第一条得知 \(a\leq c\) 有什么用呢？

发现这和我们之前求最大值有点像，因为 \(c\) 就是 \(a,b,c\) 中最大的值了。

这样如果做完整个数列，我们就知道整个数列最大的值了。

现在除了某些0和最大值我们一无所知，不过我们知道剩余所有数的大小关系。为了方便描述，我们将他排成一条链。

发现这样和 Subtask 3 相同，也就是：

二分中点 mid，以其为 \(c\) ，比其小的（设位置为 mid-1 ）为 \(b\) 。

通过比较可知这两个位置的数。于是可以求出0,1的交界点。

注意到二分到某个数的时候无法确定，于是再次用奇偶性判断。

原文地址：http://www.cnblogs.com/gyyyyy/p/16866811.html