← 返回题目列表

Codeforces · 1157/E

E. 最小数组

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

给定两个数组 $$$a$$$ 和 $$$b$$$,长度均为 $$$n$$$。两个数组的所有元素都从 $$$0$$$ 到 $$$n-1$$$。

您可以对数组 $$$b$$$ 的元素重新排序(如果需要,您可以保持元素的顺序不变)。之后,令数组 $$$c$$$ 为长度为 $$$n$$$ 的数组,该数组的第 $$$i$$$ 个元素为 $$$c_i = (a_i + b_i) \% n$$$,其中 $$$x \% y$$$ 为 $$$x$$$ 对 $$$y$$$ 求模。

您的任务是对数组 $$$b$$$ 的元素重新排序,以获得按字典顺序排列的最小可能数组 $$$c$$$。

长度为 $$$n$$$ 的数组 $$$x$$$ 按字典顺序小于长度为 $$$n$$$ 的数组 $$$y$$$,如果存在这样的 $$$i$$$ ($$$1 \le i \le n$$$),$$$x_i < y_i$$$,并且对于任何 $$$j$$$ ($$$1 \le j < i$$$) $$$x_j = y_j$$$。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — $$$a$$$、$$$b$$$ 和 $$$c$$$ 中的元素数量。

输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i < n$$$),其中 $$$a_i$$$ 是 $$$a$$$ 的第 $$$i$$$ 个元素。

输入的第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$0 \le b_i < n$$$),其中 $$$b_i$$$ 是 $$$b$$$ 的第 $$$i$$$ 个元素。

输出

打印按字典顺序排列的最小可能数组 $$$c$$$。回想一下,您的任务是对数组 $$$b$$$ 的元素进行重新排序,并获取按字典顺序排列的最小可能数组 $$$c$$$,其中 $$$c$$$ 的第 $$$i$$$ 元素是 $$$c_i = (a_i + b_i) \% n$$$。

示例

输入 #1

4
0 1 2 1
3 2 1 1

输出 #1

1 0 0 2

输入 #2

7
2 5 1 5 3 4 3
2 4 3 5 6 5 1

输出 #2

0 0 0 1 0 2 4