← 返回题目列表

Codeforces · 1895/E

E. 无限卡牌游戏

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

Monocarp 和 Bicarp 正在玩纸牌游戏。每张卡都有两个参数:攻击值和防御值。如果$$$s$$$ 的攻击严格大于$$$t$$$ 的防御,则一张牌$$$s$$$ 会击败另一张牌$$$t$$$。

Monocarp 有 $$$n$$$ 卡,其中第 $$$i$$$ 的攻击值为 $$$\mathit{ax}_i$$$,防御值为 $$$\mathit{ay}_i$$$。 Bicarp 有 $$$m$$$ 卡,其中第 $$$j$$$ 的攻击值为 $$$\mathit{bx}_j$$$,防御值为 $$$\mathit{by}_j$$$。

在第一步中,Monocarp 选择他的一张牌并打出它。比卡普必须用他自己的牌来回应,打败那张牌。之后,Monocarp 必须用一张击败 Bicarp 的牌来回应。之后,轮到比卡普了,依此类推。

一张牌被击败后,它会回到打出它的玩家的手上。这意味着每个玩家始终拥有与游戏开始时相同的牌组。当当前玩家没有牌可以击败对手刚刚打出的牌时,游戏结束,当前玩家输。

如果游戏持续 $$$100^{500}$$$ 步,则宣布平局。

Monocarp 和 Bicarp 都能发挥最佳效果。也就是说,如果一名玩家无论对手如何行动都有获胜策略,那么他就是为了胜利而下棋。否则,如果他有平局策略,他就会为平局而打。

您需要计算三个值:

- Monocarp 获胜的起始动作数量;
- Monocarp 的起始动作导致平局的次数;
- Monocarp 导致 Bicarp 获胜的起始动作数量。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — Monocarp 拥有的卡片数量。

第二行包含 $$$n$$$ 整数 $$$\mathit{ax}_1, \mathit{ax}_2, \dots, \mathit{ax}_n$$$ ($$$1 \le \mathit{ax}_i \le 10^6$$$) — Monocarp 卡牌的攻击值。

第三行包含 $$$n$$$ 整数 $$$\mathit{ay}_1, \mathit{ay}_2, \dots, \mathit{ay}_n$$$ ($$$1 \le \mathit{ay}_i \le 10^6$$$) — Monocarp 卡牌的防御值。

第四行包含一个整数 $$$m$$$ ($$$1 \le m \le 3 \cdot 10^5$$$) — Bicarp 拥有的牌数。

第五行包含 $$$m$$$ 整数 $$$\mathit{bx}_1, \mathit{bx}_2, \dots, \mathit{bx}_m$$$ ($$$1 \le \mathit{bx}_j \le 10^6$$$) — Bicarp 卡牌的攻击值。

第六行包含 $$$m$$$ 整数 $$$\mathit{by}_1, \mathit{by}_2, \dots, \mathit{by}_m$$$ ($$$1 \le \mathit{by}_j \le 10^6$$$) – Bicarp 牌的防御值。

输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$,所有测试用例的 $$$m$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,打印三个整数:

- Monocarp 获胜的起始动作数量;
- Monocarp 的起始动作导致平局的次数;
- Monocarp 导致 Bicarp 获胜的起始动作数量。

示例

输入 #1

3
3
8 7 4
7 1 10
2
8 4
5 10
9
8 8 5 5 5 4 4 1 4
2 7 5 2 8 9 7 1 9
10
9 8 7 6 5 5 4 3 2 1
7 1 6 7 5 8 8 4 9 6
1
10
5
1
10
5

输出 #1

1 1 1
2 4 3
0 1 0