1157E.md (1668B)
1 Source: https://codeforces.com/problemset/problem/1157/E 2 3 E. Minimum Array 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given two arrays $a$ and $b$, both of length $n$. All elements of both arrays are from $0$ to $n-1$. 22 23 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$. 24 25 Your task is to reorder elements of the array $b$ to obtain the lexicographically minimum possible array $c$. 26 27 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 \lt y_i$, and for any $j$ ($1 \le j \lt i$) $x_j = y_j$. 28 29 Input 30 31 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$. 32 33 The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \lt n$), where $a_i$ is the $i$-th element of $a$. 34 35 The third line of the input contains $n$ integers $b_1, b_2, \dots, b_n$ ($0 \le b_i \lt n$), where $b_i$ is the $i$-th element of $b$. 36 37 Output 38 39 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$. 40 41 Examples 42 43 Input 44 45 ``` 46 4 47 0 1 2 1 48 3 2 1 1 49 ``` 50 51 Output 52 53 ``` 54 1 0 0 2 55 ``` 56 57 Input 58 59 ``` 60 7 61 2 5 1 5 3 4 3 62 2 4 3 5 6 5 1 63 ``` 64 65 Output 66 67 ``` 68 0 0 0 1 0 2 4 69 ```