306174: CF1157E. Minimum Array

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Minimum Array

题意翻译

题目描述 给定两个长度为n的序列a和b,可以对b进行任意顺序变换,得到序列c.对于序列c,ci=(ai+bi)%n 求得字典序最小的c序列方案。

题目描述

You are given two arrays $ a $ and $ b $ , both of length $ n $ . All elements of both arrays are from $ 0 $ to $ n-1 $ . You can reorder elements of the array $ b $ (if you want, you may leave the order of elements as it is). After that, let array $ c $ be the array of length $ n $ , the $ i $ -th element of this array is $ c_i = (a_i + b_i) \% n $ , where $ x \% y $ is $ x $ modulo $ y $ . Your task is to reorder elements of the array $ b $ to obtain the lexicographically minimum possible array $ c $ . Array $ x $ of length $ n $ is lexicographically less than array $ y $ of length $ n $ , if there exists such $ i $ ( $ 1 \le i \le n $ ), that $ x_i < y_i $ , and for any $ j $ ( $ 1 \le j < i $ ) $ x_j = y_j $ .

输入输出格式

输入格式


The first line of the input contains one integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the number of elements in $ a $ , $ b $ and $ c $ . The second line of the input contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 0 \le a_i < n $ ), where $ a_i $ is the $ i $ -th element of $ a $ . The third line of the input contains $ n $ integers $ b_1, b_2, \dots, b_n $ ( $ 0 \le b_i < n $ ), where $ b_i $ is the $ i $ -th element of $ b $ .

输出格式


Print the lexicographically minimum possible array $ c $ . Recall that your task is to reorder elements of the array $ b $ and obtain the lexicographically minimum possible array $ c $ , where the $ i $ -th element of $ c $ is $ 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 

Input

题意翻译

题目描述 给定两个长度为n的序列a和b,可以对b进行任意顺序变换,得到序列c.对于序列c,ci=(ai+bi)%n 求得字典序最小的c序列方案。

加入题单

上一题 下一题 算法标签: