Algorithm

E. Minimum Array
time limit per test
2 seconds
memory limit per test
256 megabytes
Problem link- https://codeforces.com/contest/1157/problem/E
input
standard input
output
standard output

You are given two arrays a� and b�, both of length n�. All elements of both arrays are from 00 to n−1�−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 ci=(ai+bi)%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≤i≤n1≤�≤�), that xi<yi��<��, and for any j� (1≤j<i1≤�<�) xj=yj��=��.

Input

The first line of the input contains one integer n� (1≤n≤2⋅1051≤�≤2⋅105) — the number of elements in a�, b� and c�.

The second line of the input contains n� integers a1,a2,…,an�1,�2,…,�� (0≤ai<n0≤��<�), where ai�� is the i�-th element of a�.

The third line of the input contains n� integers b1,b2,…,bn�1,�2,…,�� (0≤bi<n0≤��<�), where bi�� is the i�-th element of b�.

Output

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 ci=(ai+bi)%n��=(��+��)%�.

Examples
input
Copy
4
0 1 2 1
3 2 1 1
output
Copy
1 0 0 2
input
Copy
7
2 5 1 5 3 4 3
2 4 3 5 6 5 1
output
Copy
0 0 0 1 0 2 4

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int const N = 2e5 + 1;
int n, a[N], b[N];
multiset<int>
 st;

int main() {
  scanf("%d", &n);
  for(int i = 0; i < n; ++i)
    scanf("%d", a + i);
  for(int i = 0; i < n; ++i)
    scanf("%d", b + i), st.insert(b[i]);
  
  for(int i = 0, need; i < n; ++i) {
    need = n - a[i];
    multiset<int>
::iterator it = st.lower_bound(need);
    if(it == st.end())
      it = st.begin();
    
    printf("%s%d", i == 0 ? "" : " ", (a[i] + (*it)) % n);

    st.erase(it);
  }

  puts("");

  return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
4
0 1 2 1
3 2 1 1

Output

x
–
+
cmd
1 0 0 2
Advertisements

Demonstration

Codeforcces Solution E. Minimum Array -Solution in C, C++, Java, Python

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+