← 返回题目列表

Codeforces · 1214/F

F. 就业

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

两家大公司“Cecsi”和“Poca Pola”长期相互对抗。为了战胜竞争对手,“Poca Pola”启动了一个超级秘密项目,为此它在所有办公室中总共有$$$n$$$的空缺。经过多次测试和面试,候选人被选中,剩下的就是他们的工作了。

由于所有候选人都拥有相同的技能,因此他们在哪里工作并不重要。这就是为什么公司决定在工作场所之间分配候选人,以使所有候选人的家庭和工作场所之间的总距离最小。

众所周知,地球是圆的,因此可以描述为一个圆,地球上所有$$$m$$$城市都可以描述为这个圆上的点。所有城市均从 $$$1$$$ 到 $$$m$$$ 进行枚举,因此对于每个 $$$i$$$ ($$$1 \le i \le m - 1$$$) ,索引为 $$$i$$$ 和 $$$i + 1$$$ 的城市是邻居,索引为 $$$1$$$ 和 $$$m$$$ 的城市也是邻居。人只能沿着圆圈移动。任意两个城市之间的距离等于从一个城市到另一个城市所需执行的相邻城市之间的最少转乘次数。特别是,城市与其本身之间的距离等于 $$$0$$$。

“Poca Pola”职位空缺位于 $$$a_1、a_2、\ldots、a_n$$$ 城市的办事处。候选人居住在城市$$$b_1、b_2、\ldots、b_n$$$。有可能一些职位空缺位于同一城市,而一些候选人则居住在同一城市。

“Poca Pola”经理们忙于超级秘密项目,因此请您帮助“Poca Pola”在工作场所之间分配候选人,使所有候选人的家庭和工作地点之间的距离总和尽可能小。

输入

第一行包含两个整数 $$$m$$$ 和 $$$n$$$ ($$$1 \le m \le 10^9$$$, $$$1 \le n \le 200\,000$$$) — 地球上的城市数量和职位空缺数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, a_3, \ldots, a_n$$$ ($$$1 \le a_i \le m$$$) — 职位空缺所在的城市。

第三行包含 $$$n$$$ 整数 $$$b_1, b_2, b_3, \ldots, b_n$$$ ($$$1 \le b_i \le m$$$) — 候选人居住的城市。

输出

第一行应包含所有候选人从家到工作场所之间的最小总距离。

第二行应包含 $$$n$$$ 从 $$$1$$$ 到 $$$n$$$ 的不同整数。其中第 $$$i$$$ 应该是应在第 $$$i$$$ 工作场所工作的候选人的索引。

示例

输入 #1

10 3
1 5 5
10 4 6

输出 #1

3
1 2 3

输入 #2

10 3
1 4 8
8 3 6

输出 #2

4
2 3 1

注意

在第一个示例中,每个候选人与其工作场所之间的距离等于 $$$1$$$(从 $$$1$$$ 到 $$$10$$$、从 $$$4$$$ 到 $$$5$$$ 以及从 $$$6$$$ 到 $$$5$$$)。

在第二个示例中:

- 第二个候选人在第一个工作地点工作,城市 $$$3$$$ 和 $$$1$$$ 之间的距离等于 $$$2$$$。
- 第三个候选人在第二个工作地点工作,城市 $$$6$$$ 和 $$$4$$$ 之间的距离等于 $$$2$$$。
- 第一个候选人在第三个工作地点工作,城市 $$$8$$$ 和 $$$8$$$ 之间的距离等于 $$$0$$$。