CF940D Alena And The Heater

“我们已经尝试了单独禁闭、水刑，甚至让他听 Just In Beaver 的歌，但都无济于事。我们需要一些极端的手段。” “小 Alena 收到了一个数组作为生日礼物……” 长度为 $n$ 的数组 $b$ 是通过如下过程，由长度为 $n$ 的数组 $a$ 和两个整数 $l$、$r$（$l \leq r$）得到的： $b_1 = b_2 = b_3 = b_4 = 0$。 对于所有 $5 \leq i \leq n$： - 如果 $a_i, a_{i-1}, a_{i-2}, a_{i-3}, a_{i-4} > r$ 且 $b_{i-1} = b_{i-2} = b_{i-3} = b_{i-4} = 1$，则 $b_i = 0$； - 如果 $a_i, a_{i-1}, a_{i-2}, a_{i-3}, a_{i-4} < l$ 且 $b_{i-1} = b_{i-2} = b_{i-3} = b_{i-4} = 0$，则 $b_i = 1$； - 否则 $b_i = b_{i-1}$。 现在给定数组 $a$ 和 $b'$（长度均为 $n$），请你找到两个整数 $l$ 和 $r$（$l \leq r$），使得按照上述算法得到的数组 $b$ 恰好等于 $b'$。 保证一定存在解。

输入的第一行包含一个整数 $n$（$5 \leq n \leq 10^5$），表示 $a$ 和 $b'$ 的长度。 第二行包含 $n$ 个用空格分隔的整数 $a_1, \ldots, a_n$（$-10^9 \leq a_i \leq 10^9$），表示数组 $a$ 的元素。 第三行包含一个长度为 $n$ 的仅由 $0$ 和 $1$ 组成的字符串，表示数组 $b'$ 的元素。注意这些数字之间没有空格。

输出两个整数 $l$ 和 $r$（$-10^9 \leq l \leq r \leq 10^9$），满足题目要求。 如果有多组解，输出任意一组均可。 保证一定存在解。

在第一个测试样例中，任意满足 $6 \leq l \leq r \leq 10^9$ 的 $l$ 和 $r$ 都是合法的，此时 $b_5 = 1$，因为 $a_1, \ldots, a_5 < l$。 由 ChatGPT 4.1 翻译