#P10220. [省选联考 2024] 迷宫守卫

[省选联考 2024] 迷宫守卫

题目描述

Alice 拥有一座迷宫,这座迷宫可以抽象成一棵拥有 2n2^n 个叶节点的满二叉树,总节点数目为 (2n+11)(2^{n+1} - 1),依次编号为 1(2n+11)1 \sim (2^{n+1} - 1)。其中编号为 2n(2n+11)2^n \sim (2^{n+1} - 1) 的是叶节点,编号为 1(2n1)1 \sim (2^n - 1) 的是非叶节点,且非叶节点 1u(2n1)1 \le u \le (2^n - 1) 的左儿子编号为 2u2u,右儿子编号为 (2u+1)(2u + 1)

每个非叶节点都有一个石像守卫,初始时,所有石像守卫均在沉睡。唤醒 uu 点的石像守卫需要 wuw_u 的魔力值。

每个叶节点都有一个符文,vv 点的符文记作 qvq_v保证 q2n,q2n+1,,q2n+11q_{2^n}, q_{2^n+1},\cdots, q_{2^{n+1}-1} 构成 12n1 \sim 2^n 的排列

探险者初始时持有空序列 QQ,从节点 11 出发,按照如下规则行动:

  • 到达叶节点 vv 时,将 vv 点的符文 qvq_v 添加到序列 QQ 的末尾,然后返回父节点。
  • 到达非叶节点 uu 时:
    • 若该点的石像守卫已被唤醒,则只能先前往左儿子,(从左儿子返回后)再前往右儿子,(从右儿子返回后)最后返回父节点。
    • 若该点的石像守卫在沉睡,可以在以下二者中任选其一:
      • 先前往左儿子,再前往右儿子,最后返回父节点。
      • 先前往右儿子,再前往左儿子,最后返回父节点。

返回节点 11 时,探险结束。可以证明,探险者一定访问每个叶节点各一次,故此时 QQ 的长度为 2n2^n

探险者 Bob 准备进入迷宫,他希望探险结束时的 QQ 的字典序越小越好,与之相对,Alice 希望 QQ 的字典序越大越好。

在 Bob 出发之前,Alice 可以选择一些魔力值花费之和不超过 KK 的石像守卫,并唤醒它们。Bob 出发时,他能够知道 Alice 唤醒了哪些神像。若双方都采取最优策略,求序列 QQ 的最终取值。

对于两个长度为 2n2^n 的序列 Q1,Q2Q_1,Q_2,称 Q1Q_1 字典序小于 Q2Q_2 当且仅当以下条件成立:

  • i[1,2n]\exist i \in [1, 2^n] 满足以下两个条件:
    • 1j<iQ1,j=Q2,j\forall 1 \le j < i,Q_{1,j} = Q_{2,j}
    • Q1,i<Q2,iQ_{1,i} < Q_{2,i}

输入格式

本题有多组测试数据。输入的第一行包含一个正整数 TT,表示测试数据组数。

接下来依次 TT 组测试数据。对于每组测试数据:

  • 第一行两个整数 n,Kn,K 表示迷宫规模和 Alice 可用于唤醒石像守卫的魔力值上限。
  • 第二行 (2n1)(2^n - 1) 个整数 w1,w2,,w2n1w_1,w_2,\cdots,w_{2^n-1} 表示唤醒各个石像守卫耗费的魔力值。
  • 第三行 2n2^n 个整数 q2n,q2n+1,,q2n+11q_{2^n}, q_{2^n+1},\cdots, q_{2^{n+1}-1} 表示各个叶节点上的符文。

输出格式

对于每组数据,输出一行 2n2^n 个整数 Q1,Q2,,Q2nQ_1,Q_2,\cdots,Q_{2^n},表示双方都采取最优策略的情况下,序列 QQ 的最终取值。

3
1 0
1
2 1
1 1
1
2 1
3 3
3 2 1 2 1 2 1
4 2 6 3 7 1 5 8
1 2
2 1
2 4 6 3 5 8 7 1

提示

【样例 1 解释】

  • 第一组数据中,Alice 无法唤醒石像守卫,Bob 可以选择先访问叶节点 33,再访问叶节点 22,得 Q={1,2}Q = \{1, 2\}
  • 第二组数据中,Alice 可以唤醒节点 11 的石像守卫,Bob 只能先访问叶节点 22,再访问叶节点 33,得 Q={2,1}Q = \{2, 1\}
  • 第三组数据中,Alice 的最优策略是唤醒节点 5,65, 6 的石像守卫。

【样例 2】

见附件中的 maze2.in/ans

该组数据满足特殊性质 A。

【样例 3】

见附件中的 maze3.in/ans

该组数据满足特殊性质 B。

【样例 4】

见附件中的 maze4.in/ans

【样例 5】

见附件中的 maze5.in/ans

【子任务】

2n\sum 2^n 表示单个测试点钟所有测试数据的 2n2^n 的和。对于所有测试数据,保证

  • 1T1001\le T \le 100
  • 1n161\le n \le 1612n1051 \le \sum 2^n \le 10^5
  • 0K10120\le K \le 10^{12}
  • 1u(2n1)\forall 1 \le u \le (2^n-1)0wu10120 \le w_u \le 10^{12}
  • q2n,q2n+1,,q2n+11q_{2^n},q_{2^n+1},\cdots,q_{2^{n+1}-1} 构成 12n1\sim 2^n 的排列。
测试点编号 nn\le 2n\sum 2^n \le 特殊性质
151\sim 5 44 8080
66 66 200200 A
787\sim 8 B
9109\sim 10
1111 1111 40004000 A
121312\sim 13 B
141514\sim 15
1616 1616 10510^5 A
171817\sim 18 B
192019\sim 20

特殊性质 A:2nv(2n+11)\forall 2^n \le v \le (2^{n+1}-1)qv=(2n+1v)q_v = (2^{n+1}-v)

特殊性质 B:1u(2n1)\forall 1 \le u \le (2^n-1)wu=1w_u = 1