English · Original
Chinese · Translation
Formal · Original
It's marriage season in Ringland!
Ringland has a form of a circle's boundary of length $L$. There are $n$ bridegrooms and $n$ brides, and bridegrooms decided to marry brides.
Of course, each bridegroom should choose exactly one bride, and each bride should be chosen by exactly one bridegroom.
All objects in Ringland are located on the boundary of the circle, including the capital, bridegrooms' castles and brides' palaces. The castle of the $i$\-th bridegroom is located at the distance $a_i$ from the capital in clockwise direction, and the palace of the $i$\-th bride is located at the distance $b_i$ from the capital in clockwise direction.
Let's define the inconvenience of a marriage the maximum distance that some bride should walk along the circle from her palace to her bridegroom's castle in the shortest direction (in clockwise or counter-clockwise direction).
Help the bridegrooms of Ringland to choose brides in such a way that the inconvenience of the marriage is the smallest possible.
## Input
The first line contains two integers $n$ and $L$ ($1 \leq n \leq 2 \cdot 10^{5}$, $1 \leq L \leq 10^{9}$) — the number of bridegrooms and brides and the length of Ringland.
The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i < L$) — the distances from the capital to the castles of bridegrooms in clockwise direction.
The next line contains $n$ integers $b_1, b_2, \ldots, b_n$ ($0 \leq b_i < L$) — the distances from the capital to the palaces of brides in clockwise direction.
## Output
In the only line print the smallest possible inconvenience of the wedding, where the inconvenience is the largest distance traveled by a bride.
[samples]
## Note
In the first example the first bridegroom should marry the second bride, the second bridegroom should marry the first bride. This way, the second bride should walk the distance of $1$, and the first bride should also walk the same distance. Thus, the inconvenience is equal to $1$.
In the second example let $p_i$ be the bride the $i$\-th bridegroom will marry. One of optimal $p$ is the following: $(6,8,1,4,5,10,3,2,7,9)$.
Ringland 正处于婚季！
Ringland 的形状是一个周长为 $L$ 的圆。有 $n$ 位新郎和 $n$ 位新娘，新郎们决定与新娘结婚。
当然，每位新郎应恰好选择一位新娘，每位新娘也应恰好被一位新郎选择。
Ringland 中的所有物体都位于圆的边界上，包括首都、新郎的城堡和新娘的宫殿。第 $i$ 位新郎的城堡位于从首都顺时针方向距离 $a_i$ 处，第 $i$ 位新娘的宫殿位于从首都顺时针方向距离 $b_i$ 处。
我们定义一场婚姻的不便程度为：某位新娘从她的宫殿走到她新郎城堡所经过的最短路径（顺时针或逆时针方向）中的最大距离。
请帮助 Ringland 的新郎们选择新娘，使得婚姻的不便程度最小。
第一行包含两个整数 $n$ 和 $L$（$1 lt.eq n lt.eq 2 dot.op 10^5$，$1 lt.eq L lt.eq 10^9$）——新郎和新娘的数量以及 Ringland 的长度。
接下来一行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n$（$0 lt.eq a_i < L$）——新郎城堡从首都顺时针方向的距离。
接下来一行包含 $n$ 个整数 $b_1, b_2, dots.h, b_n$（$0 lt.eq b_i < L$）——新娘宫殿从首都顺时针方向的距离。
请在唯一一行中输出婚礼可能的最小不便程度，其中不便程度定义为新娘行走的最大距离。
在第一个例子中，第一位新郎应与第二位新娘结婚，第二位新郎应与第一位新娘结婚。这样，第二位新娘需要行走距离 $1$，第一位新娘也需要行走相同的距离。因此，不便程度为 $1$。
在第二个例子中，设 $p_i$ 表示第 $i$ 位新郎将迎娶的新娘编号。其中一个最优的 $p$ 为：$(6, 8, 1, 4, 5, 10, 3, 2, 7, 9)$。
## Input
第一行包含两个整数 $n$ 和 $L$（$1 lt.eq n lt.eq 2 dot.op 10^5$，$1 lt.eq L lt.eq 10^9$）——新郎和新娘的数量以及 Ringland 的长度。接下来一行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n$（$0 lt.eq a_i < L$）——新郎城堡从首都顺时针方向的距离。接下来一行包含 $n$ 个整数 $b_1, b_2, dots.h, b_n$（$0 lt.eq b_i < L$）——新娘宫殿从首都顺时针方向的距离。
## Output
请在唯一一行中输出婚礼可能的最小不便程度，其中不便程度定义为新娘行走的最大距离。
[samples]
## Note
在第一个例子中，第一位新郎应与第二位新娘结婚，第二位新郎应与第一位新娘结婚。这样，第二位新娘需要行走距离 $1$，第一位新娘也需要行走相同的距离。因此，不便程度为 $1$。在第二个例子中，设 $p_i$ 表示第 $i$ 位新郎将迎娶的新娘编号。其中一个最优的 $p$ 为：$(6, 8, 1, 4, 5, 10, 3, 2, 7, 9)$。
**Definitions**
Let $ n \in \mathbb{Z}^+ $, $ L \in \mathbb{Z}^+ $.
Let $ A = (a_1, a_2, \dots, a_n) $, $ B = (b_1, b_2, \dots, b_n) $ be two sequences of points on the circle of circumference $ L $, where $ a_i, b_j \in [0, L) $.
Let $ \pi : \{1, \dots, n\} \to \{1, \dots, n\} $ be a permutation representing the assignment of bridegroom $ i $ to bride $ \pi(i) $.
Define the circular distance between two points $ x, y \in [0, L) $ as:
$$
d(x, y) = \min\left( |x - y|, L - |x - y| \right)
$$
**Constraints**
1. $ 1 \le n \le 2 \cdot 10^5 $
2. $ 1 \le L \le 10^9 $
3. $ 0 \le a_i < L $, $ 0 \le b_j < L $ for all $ i, j \in \{1, \dots, n\} $
**Objective**
Find a permutation $ \pi $ minimizing:
$$
\max_{i \in \{1, \dots, n\}} d(a_i, b_{\pi(i)})
$$
API Response (JSON)
{
"problem": {
"name": "F. Round Marriage",
"description": {
"content": "It's marriage season in Ringland! Ringland has a form of a circle's boundary of length $L$. There are $n$ bridegrooms and $n$ brides, and bridegrooms decided to marry brides. Of course, each bridegr",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 3000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF981F"
},
"statements": [
{
"statement_type": "Markdown",
"content": "It's marriage season in Ringland!\n\nRingland has a form of a circle's boundary of length $L$. There are $n$ bridegrooms and $n$ brides, and bridegrooms decided to marry brides.\n\nOf course, each bridegr...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Ringland 正处于婚季！\n\nRingland 的形状是一个周长为 $L$ 的圆。有 $n$ 位新郎和 $n$ 位新娘，新郎们决定与新娘结婚。\n\n当然，每位新郎应恰好选择一位新娘，每位新娘也应恰好被一位新郎选择。\n\nRingland 中的所有物体都位于圆的边界上，包括首都、新郎的城堡和新娘的宫殿。第 $i$ 位新郎的城堡位于从首都顺时针方向距离 $a_i$ 处，第 $i$ 位新娘的宫殿位于从首...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $, $ L \\in \\mathbb{Z}^+ $. \nLet $ A = (a_1, a_2, \\dots, a_n) $, $ B = (b_1, b_2, \\dots, b_n) $ be two sequences of points on the circle of circumference $ L...",
"is_translate": false,
"language": "Formal"
}
]
}