在对高中物理学进行了整个学习之后,辛迪打算运用他的知识。他挖出了一块印制电路板,上面有2排触点,每排有n+1个。他计划用细铜线连接这些触点,如下图所示(蓝色是触点,红色是电线,电源没有连接),然后计算电阻和电流。连接下图中的两个相邻节点需要1单位长度的铜线。为了实现这一目标,辛迪从鲍勃借用了一些总长度为3n的铜线。辛迪可以将每根铜线弯曲数次,但不能将任何铜线掰开。请为辛迪找到任何有效的解决方案,或者报告不可能!
Implementation Details
你应该包含 circuit.h,并实现如下过程:
int[][] wiring(int n, int[] w)
- $n$: 每行的长度,见题面。
- $w$: 第 $i$ 个($0\le i\le n-1$)表示一条长度为 $w[i]>0$ 的铜线。保证 $w$ 内元素之和为 $3n$。
- 你实现的过程会被调用恰好一次。
- 如果无解,你应该返回一个空数组。
- 否则,你应该返回一个由三个 $n$ 长度的数组组成的数组,依次表示第一排横着的、竖着的、第二排横着的每个单位线段从左到右由哪条铜线组成($0$ 到 $n-1$ 的编号)。
Example
考虑如下调用:wiring(3, [3, 2, 2, 2])
一种合法的输出为 [[0, 0, 2], [0, 1, 2], [1, 3, 3]],对应下图。
Constraints
$1\le n,|w|\le 10^5$
$\sum_{t\in w} t=3n$
Subtasks
- (10分)$n\le 3$,$m\le 9$
- (20分)所有铜线长度至多为2
- (30分)所有铜线长度至少为2
- (20分)$n,m\le 5000$
- (20分)无特殊限制。
Sample Grader
样例交互器以下列格式读取输入。
- 第一行:$n~|w|$
- 第二行:依次给出 $w$ 的各个元素
样例交互器以下列格式打印你的输出。
- 第一行:如果有解输出
Yes,否则输出No - 如果有解,接下来三行依次输出返回的方案