CF1428D Bouncing Boomerangs

为了提升动物们投掷回旋镖的技巧，动物管理员在一个 $n \times n$ 的网格上设置了一些靶子，其中每一行和每一列最多只能有 $2$ 个靶子。网格的行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $n$。 对于每一列，动物管理员会从该列的底部（网格下方）向上投掷回旋镖。当回旋镖击中任意一个靶子时，会弹开并向右转 $90$ 度，然后沿新的方向直线飞行。回旋镖可以击中多个靶子，直到飞出网格才会停止。  在上图中，$n=6$，黑色叉号表示靶子。第 $1$ 列的回旋镖（蓝色箭头）弹跳了 $2$ 次，第 $3$ 列的回旋镖（红色箭头）弹跳了 $3$ 次。 第 $i$ 列的回旋镖恰好击中了 $a_i$ 个靶子后才飞出网格。已知 $a_i \leq 3$。 然而，动物管理员已经忘记了靶子的原始位置。因此，他请求你构造一个满足每列击中次数的有效靶子分布，或者告诉他不存在这样的分布。如果存在多个有效分布，你可以输出任意一个。

第一行包含一个整数 $n$，$1 \leq n \leq 10^5$。 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，$0 \leq a_i \leq 3$。

如果不存在有效的靶子分布，输出 $-1$。 否则，第一行输出一个整数 $t$，表示你构造的靶子的总数，$0 \leq t \leq 2n$。 接下来 $t$ 行，每行输出两个用空格分隔的整数 $r$ 和 $c$，表示一个靶子在第 $r$ 行第 $c$ 列，$1 \leq r,c \leq n$。所有靶子的位置必须互不相同。 你构造的分布中，每一行和每一列最多只能有 $2$ 个靶子。

对于第一个测试点，答案的分布与题目中的图片相同。 对于第二个测试点，回旋镖不会击中任何靶子，因此可以不放置任何靶子。 对于第三个测试点，以下的靶子分布虽然满足每列击中次数，但第 $3$ 行有 $4$ 个靶子，不合法。  可以证明，对于这个测试点，不存在任何有效的靶子分布能满足给定的击中次数。 由 ChatGPT 4.1 翻译