Bea the maximizer
本题没有可用的提交语言。
Description
Bea has two arrays $a$ and $b$, both of $n$ integers.
A permutation of length $n$ is an array of length $n$ where each number between $1$ and $n$ appears exactly once.
Your task is to find a permutation $p$ of length $n$ which maximizes the following value:
$(a_1 + b_{p_1})$ $\&$ $(a_2 + b_{p_2})$ $\&$ ... $\&$ $(a_n + b_{p_n})$.
$\&$ is the bitwise AND operator, If you don't know how it works, remember that you can search for it on the internet ;)
As there can be a lot of solutions, Bea also wants to find one that minimizes the maximum distance from the position of a value on the chosen permutation to it's original position in the sorted permutation, in other words, Bea wants to find one that minimizes the following value: $\max_{1 \leq i \leq n} (|i - pos_i|)$ where $pos_i$ is position of $i$ in the chosen permutation and $|x|$ is the absolute value of $x$.
Please, help Bea :(
Each test contains multiple test cases. The first line contains the number of test cases $t$ $(1 \leq t \leq 100)$. The description of the test cases follows.
The first line consists in one integer $n$ $(2 \leq n \leq 1500)$ — the size of the arrays.
Then follows $n$ integers $a_{i}$ $(0 \leq a_{i} \leq 10^{9})$ — the values of $a$.
Finally follows $n$ integers $b_{i}$ $(0 \leq b_{i} \leq 10^{9})$ — the values of $b$.
It is guaranteed that the sum of $n$ over all test cases does not exceed $1500$.
For each testcase, output two integers per line, the maximum possible value chosing the permutation optimally, and the minimum maximum distance from the position of a value on the chosen permutation to it's original position in the sorted permutation, so that the maximum value continues to be obtained.
Input
Each test contains multiple test cases. The first line contains the number of test cases $t$ $(1 \leq t \leq 100)$. The description of the test cases follows.
The first line consists in one integer $n$ $(2 \leq n \leq 1500)$ — the size of the arrays.
Then follows $n$ integers $a_{i}$ $(0 \leq a_{i} \leq 10^{9})$ — the values of $a$.
Finally follows $n$ integers $b_{i}$ $(0 \leq b_{i} \leq 10^{9})$ — the values of $b$.
It is guaranteed that the sum of $n$ over all test cases does not exceed $1500$.
Output
For each testcase, output two integers per line, the maximum possible value chosing the permutation optimally, and the minimum maximum distance from the position of a value on the chosen permutation to it's original position in the sorted permutation, so that the maximum value continues to be obtained.
4
5
5 13 4 10 0
3 0 2 11 15
3
7 1 2
5 8 1
3
1 2 3
5 4 6
2
1000000000 1000000000
1000000000 1000000000
8 1
2 1
7 2
2000000000 0
Note
—
Problem idea: danx
Problem preparation: danx
Ocurrences: Advanced 9