Preparando MOJI
The final of Berland Chess Team Championship is going to be held soon. Two teams consisting of $$$n$$$ chess players each will compete for first place in the tournament. The skill of the $$$i$$$-th player in the first team is $$$a_i$$$, and the skill of the $$$i$$$-th player in the second team is $$$b_i$$$. The match will be held as follows: each player of the first team will play a game against one player from the second team in such a way that every player has exactly one opponent. Formally, if the player $$$i$$$ from the first team opposes the player $$$p_i$$$ from the second team, then $$$[p_1, p_2, \dots, p_n]$$$ is a permutation (a sequence where each integer from $$$1$$$ to $$$n$$$ appears exactly once).
Whenever two players of almost equal skill play a game, it will likely result in a tie. Chess fans don't like ties, so the organizers of the match should distribute the players in such a way that ties are unlikely.
Let the unfairness of the match be the following value: $$$\min\limits_{i = 1}^{n} |a_i - b_{p_i}|$$$. Your task is to assign each player from the first team an opponent from the second team so that the unfairness is maximum possible (the greater it is, the smaller the probability of ties is, that's why you should maximize it).
The first line contains one integer $$$t$$$ ($$$1 \le t \le 3000$$$) — the number of test cases.
Each test case consists of three lines. The first line contains one integer $$$n$$$ ($$$1 \le n \le 3000$$$) — the number of players in each team.
The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_1 \le a_2 \le \dots \le a_n \le 10^6$$$) — the skills of players of the first team.
The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_1 \le b_2 \le \dots \le b_n \le 10^6$$$) — the skills of players of the second team.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3000$$$.
For each test case, output the answer as follows:
Print $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ on a separate line. All integers from $$$1$$$ to $$$n$$$ should occur among them exactly once. The value of $$$\min\limits_{i = 1}^{n} |a_i - b_{p_i}|$$$ should be maximum possible. If there are multiple answers, print any of them.
4 4 1 2 3 4 1 2 3 4 2 1 100 100 101 2 1 100 50 51 5 1 1 1 1 1 3 3 3 3 3
3 4 1 2 1 2 2 1 5 4 2 3 1
Informação
Provedor Codeforces
Código CF1431E
Tags
Submetido 0
BOUA! 0
Taxa de BOUA's 0%
Datas 09/05/2023 10:07:47
Relacionados