← 返回题目列表

Codeforces · 2187/E

E. 门和钥匙

中文机器翻译题面 查看原题

有$$$n+1$$$个房间排成一排,从左到右编号为$$$1$$$到$$$n+1$$$。还有$$$n$$$门,编号从$$$1$$$到$$$n$$$,其中第$$$i$$$门连接房间$$$i$$$和$$$i+1$$$。每扇门 $$$i$$$ 都有一个关联的非负整数 $$$a_i$$$。

给你一个长度为$$$n$$$的二进制字符串$$$^{\text{*}}$$$ $$$s$$$。对于每个 $$$1 \le i \le n$$$:

  • 如果 $$$s_i=\texttt{1}$$$,则房间 $$$i$$$ 最初包含 一 键。
  • 否则,$$$i$$$ 房间没有钥匙。

在第 $$$0$$$ 秒开始时,您位于 $$$1$$$ 房间,所有门均已关闭。对于每个 $$$k \ge 0$$$,以下事件将在第 $$$k$$$ 秒内按顺序发生:

  • 在第 $$$k$$$ 秒开始时,所有 $$$j$$$ 且 $$$a_j=k$$$ 的门都会打开。
  • 假设您在 $$$i$$$ 房间:
    • 如果您没有携带任何钥匙,并且 $$$i$$$ 房间中至少有一把钥匙,您可以拿起它并随身携带。
    • 如果您携带钥匙,您可以将其放在房间 $$$i$$$ 中。
  • 在第 $$$k$$$ 秒结束时:
    • 您可以搬到$$$i+1$$$房间。如果$$$i$$$ 门仍然关闭,您必须携带钥匙才能进入$$$i+1$$$ 房间。使用后钥匙将被消耗,门$$$i$$$将打开。
    • 如果$$$i \gt 1$$$,你可以移动到房间$$$i-1$$$。
    • 您可以入住 $$$i$$$ 房间。

对于任何门,无论它是如何打开的(自动或用钥匙),它都会永远保持打开状态。

您可以随时随身携带 最多 1 个 键。此外,尽管最初每个房间最多包含一把钥匙,但在此过程中,同一个房间中可能会放置多把钥匙。

对于每个 $$$1 \le i \le n$$$,找到到达房间 $$$i+1$$$ 所需的最少秒数。请注意,每个 $$$i$$$ 的答案是 独立.

$$$^{\text{*}}$$$二进制字符串是仅由 0 or 1.

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 门的数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \le a_i \le 2 \cdot 10^5$$$) - 与每个门关联的整数。

每个测试用例的第三行包含一个长度为$$$n$$$的二进制字符串$$$s$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出 $$$n$$$ 个整数,其中第 $$$i$$$ 个整数表示到达 $$$i+1$$$ 房间的最小秒数。

示例

输入
复制

5
1
0
0
1
2
0
1
114514
1
4
0 9 10 9
1101
10
0 1 4 2 3 14 10 18 7 25
1110000001

输出
复制

1
3
1
1 2 5 6
1 2 3 4 5 8 11 17 18 19

注意

在第一个测试用例中,门 $$$1$$$ 在第 $$$0$$$ 秒开始时打开。您可以在第 $$$0$$$ 秒结束时移动到 $$$2$$$ 房间,从而在第 $$$1$$$ 秒到达 $$$2$$$ 房间。

在第二个测试用例中,门 $$$1$$$ 在第 $$$2$$$-nd 秒开始时打开。您必须在 $$$1$$$ 房间等待,然后在 $$$2$$$-nd 秒结束时移动到 $$$2$$$ 房间,从而在 $$$3$$$-rd 第二秒到达 $$$2$$$ 房间。

在第三个测试用例中,您可以在$$$1$$$房间中拿起钥匙,并用它在第$$$0$$$秒打开门$$$i$$$,从而在第$$$1$$$秒到达$$$2$$$房间。