← 返回题目列表

Codeforces · 1431/E

E. 国际象棋比赛

中文机器翻译题面 查看原题

柏林国际象棋团体锦标赛决赛即将举行。两支由 $$$n$$$ 棋手组成的队伍将争夺锦标赛的第一名。第一队中第 $$$i$$$ 玩家的技能为 $$$a_i$$$,第二队中第 $$$i$$$ 玩家的技能为 $$$b_i$$$。比赛将按如下方式进行:第一队的每位球员将与第二队的一名球员进行一场比赛,并且每个球员都只有一个对手。形式上,如果第一队的玩家 $$$i$$$ 对抗第二队的玩家 $$$p_i$$$,则 $$$[p_1, p_2, \dots, p_n]$$$ 是一个排列(从 $$$1$$$ 到 $$$n$$$ 的每个整数只出现一次的序列)。

每当两个技能几乎相等的玩家玩游戏时,很可能会导致平局。国际象棋爱好者不喜欢平局,因此比赛组织者应该以不太可能出现平局的方式分配棋手。

设比赛的不公平性为以下值:$$$\min\limits_{i = 1}^{n} |a_i - b_{p_i}|$$$。你的任务是为第一队的每个球员分配一个第二队的对手,以使不公平性最大化(越大,平局的可能性越小,这就是为什么你应该最大化它)。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 3000$$$) — 测试用例的数量。

每个测试用例由三行组成。第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3000$$$) — 每支球队的球员人数。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_1 \le a_2 \le \dots \le a_n \le 10^6$$$) — 第一队球员的技能。

第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_1 \le b_2 \le \dots \le b_n \le 10^6$$$) — 第二队球员的技能。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3000$$$。

输出

对于每个测试用例,输出答案如下:

在单独的行上打印 $$$n$$$ 整数 $$$p_1, p_2, \dots, p_n$$$。从 $$$1$$$ 到 $$$n$$$ 的所有整数都应该在其中出现一次。 $$$\min\limits_{i = 1}^{n} |a_i - b_{p_i}|$$$ 的值应尽可能大。如果有多个答案,请打印其中任何一个。

示例

输入 #1

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

输出 #1

3 4 1 2
1 2
2 1
5 4 2 3 1