← 返回题目列表

AtCoder · arc182_d

D. 再次递增递减

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

分数: 700 点

问题陈述

没有两个相邻元素相同的整数序列称为 好的序列.

给你两个长度合适的序列 N: A=(A_1,A_2,\dots,A_N) 和 B=(B_1,B_2,\dots,B_N)。的每个元素 A 和 B 介于 0 和 M-1,包括在内。

您可以对 A 任意次数,可能为零:

  • 选择一个整数 i 之间 1 和 N,包括在内,并执行以下操作之一:
    • 设置 A_i \leftarrow (A_i + 1) \bmod M.
    • 设置 A_i \leftarrow (A_i - 1) \bmod M。在这里, (-1) \bmod M = M - 1.

但是,您无法执行使 A 不再是一个好的序列。

确定是否可以使 A 等于 B,如果可能的话,找到执行此操作所需的最少操作数。

约束

  • 2 \leq N \leq 2 \times 10^5
  • 2 \leq M \leq 10^6
  • 0\leq A_i,B_i< M(1\leq i\leq N)
  • A_i\ne A_{i+1}(1\leq i\leq N-1)
  • B_i\ne B_{i+1}(1\leq i\leq N-1)
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N

输出

如果目标无法实现,则打印 -1.

否则,以整数形式打印所需的最小操作数。


示例输入 1

3 9
2 0 1
4 8 1

示例输出 1

3

您可以通过以下三个操作来实现目标:

  • 设置 A_1 \leftarrow (A_1 + 1) \bmod M。现在 A = (3, 0, 1).
  • 设置 A_2 \leftarrow (A_2 - 1) \bmod M。现在 A = (3, 8, 1).
  • 设置 A_1 \leftarrow (A_1 + 1) \bmod M。现在 A = (4, 8, 1).

不可能通过两次或更少的操作来实现目标,所以答案是3。

例如,您不能设置 A_2 \leftarrow (A_2 + 1) \bmod M 在第一个操作中,因为它会使 A = (2, 1, 1),这不是一个好的序列。


示例输入 2

3 9
1 8 2
1 8 2

示例输出 2

0

A 和 B 可能从一开始就相等。


示例输入 3

24 182
128 115 133 52 166 92 164 119 143 99 54 162 86 2 59 166 24 78 81 5 109 67 172 99
136 103 136 28 16 52 2 85 134 64 123 74 64 28 85 161 19 74 14 110 125 104 180 75

示例输出 3

811