UOJ Logo Universal Online Judge

UOJ

#876. 【JOISC2024】有趣的家庭菜园 5

附件下载 统计

Bitaro,一个多年来一直热衷于园艺的人,计划从今年春天开始种植一种名为 Bita-radish 的植物。

Bitaro 已经准备好了 2N 个 Bita-radish 幼苗。这些幼苗从 12N 编号,Bitaro 计划按照这个顺序进行栽培。第 i 个幼苗(1i2N)的大小为 Ai。Bitaro 希望每个幼苗都能得到足够的阳光,因此幼苗的大小满足以下条件:

  • A1A2ANAN+1.
  • AN+1AN+2A2N1A2NA1.

注意,幼苗 1 最小,幼苗 N+1 最大。

Bitaro 还准备了 N 个红色花盆和 N 个蓝色花盆,每个花盆也有一定大小。第 j 个(1jN)红色花盆的大小是 Bj,第 k 个(1kN)蓝色花盆的大小是 Ck。Bitaro 在这总共 2N 个花盆中各种植一株 Bita-radish 幼苗,并按某种顺序排列花盆,使幼苗按 1,2,...,2N 顺序依次放入花盆中。

考虑到外观,这 2N 个花盆必须被安排在一个美观的顺序中。这里,美观的顺序意味着花盆的排列使得存在连续的 N 个花盆颜色相同。更确切地说,一个花盆排列被称为是美观的,当且仅当存在一个整数 l,满足 1lN+1,使得种植了幼苗 l,l+1,,l+N1 的花盆颜色都相同。

当尺寸为 y 的幼苗种植在尺寸为 x 的花盆中时,该对的栽培难度是绝对值 |xy|。Bitaro 种植 Bita-radish 的工作量是 2N 对花盆和幼苗中的最大栽培难度。编写一个程序,给定 Bita-radish 幼苗和花盆的信息,找到种植幼苗的最小可能 Bitaro 工作量值,并且花盆需要按美观的顺序排列。

输入格式

从标准输入中读取以下数据:

  • N
  • A1 A2 ... A2N
  • B1 B2 ... BN
  • C1 C2 ... CN

输出格式

输出一个值,种植幼苗以使花盆按美观顺序排列时 Bitaro 工作量的最小可能值。

样例解释 1

在这个样例输入中,Bitaro 可以通过以下方式种植幼苗来实现工作量为 2

  • 将幼苗 1 种植在第一个红色花盆中。这对的栽培难度是 |21|=1
  • 将幼苗 2 种植在第二个蓝色花盆中。这对的栽培难度是 |32|=1
  • 将幼苗 3 种植在第一个蓝色花盆中。这对的栽培难度是 |46|=2
  • 将幼苗 4 种植在第二个红色花盆中。这对的栽培难度是 |53|=2

种植了幼苗 23 的花盆的颜色都是蓝色,因此花盆是按美观顺序排列的。

当种植幼苗以使花盆按美观顺序排列时,无法实现工作量小于 2。因此,输出为 2

这个样例输入满足所有子任务的约束条件。

样例解释 2

这个样例输入满足子任务 2,3,4,5 的约束条件。

样例解释 3

这个样例输入满足子任务 2,3,5 的约束条件。

约束条件

  • 1N300,000.
  • 1Ai1091i2N).
  • 1Bj1091jN).
  • 1Ck1091kN).
  • A1A2ANAN+1.
  • AN+1AN+2A2N1A2NA1.
  • 所有输入值都是整数。

子任务

  1. (4 分) N5
  2. (5 分) N10
  3. (21 分) N2,000
  4. (37 分) 所有的 Ai 的值都是不同的。另外,满足 AN<A2N
  5. (33 分) 没有额外的约束条件。