← 返回题目列表

AtCoder · pakencamp_2024_day3_1_k

K. 门松

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

配点 : 100 点

問題文

(1,2,\ldots,N) 的排列。 P=(P_1,P_2,\ldots,P_N) 和 0,1 组成长度为 N-1 序列 有 C 。

这里,给定的排列 P 保证满足以下条件: 如果

  • 整数 i\ (1 \le i \le N-1) , i 是奇数 P_i < P_{i+1} 如果 i 是偶数 P_i > P_{i+1} 符合。

您应该首先将所有元素设置为 长度为 -1 准备 N-1 序列 有 b 并按任意顺序执行以下两项操作。 您可以执行此操作任意次数,最多 300000 次。

  • 类型 1:整数 交换 i\ (1 \le i \le N-1) 。 到第 P_i 和 P_{i+1} 。
  • 类型 2:整数 替换为 i\ (1 \le i \le N-1) 。 到第 P_i < P_{i+1} 如果 第 b_i = 0, P_i > P_{i+1} 如果 第 b_i=1 。 请确定是否可以做到

b=C ,如果可以,请展示一种操作方法。 如果无法执行

制約

  • 2 \leq N \leq 2 \times 10^{5}
  • P 为 (1,2,\ldots, N) 的排列。
  • 整数 i\ (1 \le i \le N-1) , i 是奇数 P_i < P_{i+1} 、 i 是偶数 P_i > P_{i+1}
  • C_i \in \lbrace 0,1 \rbrace \ (1 \le i \le N-1)
  • 所有输入均为整数

入力

输入将以以下格式从标准输入给出。

N
P_1 P_2 \ldots P_N
C_1 C_2 \ldots C_{N-1}

出力

b=C , 在一行上输出 -1 。

b=C 如果可能,减少操作次数。 按以下格式输出为 M 。

M
T_1 I_1
T_2 I_2
\vdots
T_M I_M

但是, T_k 为 k 在操作类型中 代表选择 T_k , I_k 为 k 在第二次操作中 i=I_k 。


入力例 1

4
3 4 1 2
0 0 0

出力例 1

4
2 1
2 3
1 2
2 2