题目描述
题目译自 Open Olympiad in Informatics 2025 Day2 T3 「Переворот карт / Card Flip」。
彼得和瓦西娅买了一款新的卡片游戏《翻转》。游戏包含 n 张双面卡片和 m 张单面卡片:
- 双面卡片:正面写有数字 ai,背面写有数字 bi。
- 单面卡片:正面写有一个数字 ci。
所有卡片上的数字(包括正反面)均不相同。初始时,所有卡片都正面朝上放在桌面上。在自己的回合中,玩家必须执行以下两种操作之一:
- 从桌面上移除写有剩余卡片中最小数字的卡片。
- 如果写有最小数字的卡片是双面卡片且当前正面朝上,则可以将其翻转。
赢得游戏的玩家是移除最后一张卡片的人。请确定在彼得先行的情况下,谁将赢得游戏。
输入格式
第一行包含两个整数 n 和 m (1≤n,m≤500000),分别表示双面卡片和单面卡片的数量。
第二行包含 n 个整数 a1,a2,…,an (1≤ai≤2⋅n+m),表示双面卡片正面的数字。
第三行包含 n 个整数 b1,b2,…,bn (1≤bi≤2⋅n+m),表示双面卡片背面的数字。
第四行包含 m 个整数 c1,c2,…,cm (1≤ci≤2⋅n+m),表示单面卡片上的数字。
保证从 1 到 2⋅n+m 的每个数字在数组 a、b 或 c 中恰好出现一次。
输出格式
如果彼得赢得游戏,输出 First;如果瓦西娅赢得游戏,输出 Second。
2 1
5 3
1 2
4
First
在第一个样例中,初始时桌面上有卡片 3,4,5。为了获胜,彼得在自己的回合移除卡片 3,之后瓦西娅必须移除卡片 4,因为它是单面卡片。最后,彼得移除卡片 5,此时瓦西娅无卡可移,因此彼得获胜。
1 2
2
3
4 1
Second
在第二个样例中,初始时桌面上有卡片 1,2,4。彼得必须移除卡片 1,因为它是单面卡片。接着,为了获胜,瓦西娅翻转卡片 2,此时桌面上有卡片 3 和 4。彼得必须移除翻转后的卡片 3,之后瓦西娅移除卡片 4。由于卡片已全部移除,瓦西娅获胜。
数据范围与提示
详细子任务附加限制及分值如下表所示。其中子任务 0 是样例。
| 子任务 |
分值 |
附加限制 |
子任务依赖 |
备注 |
| 1 |
12 |
n≤20,m≤10 |
0 |
|
| 2 |
13 |
n≤20 |
0,1 |
| 3 |
9 |
|
|
ai>bi |
| 4 |
10 |
maxi=1n(ai)<mini=1n(bi) |
| 5 |
6 |
区间 [min(ai,bi);max(ai,bi)] 不相交 |
| 6 |
11 |
n≤200,m≤200 |
区间 [min(ai,bi);max(ai,bi)] 嵌套或不相交 |
| 7 |
14 |
|
5,6 |
| 8 |
13 |
n≤5000,m≤5000 |
0,1,6 |
|
| 9 |
12 |
|
0∼8 |