A3726 「OOI 2025 Day 2」翻转卡片

暂无评定 传统题 国际知名赛事 上传者
时间限制1000ms
内存限制256MiB
通过 / 提交0/0

A3726「OOI 2025 Day 2」翻转卡片

暂无评定 传统题 国际知名赛事 上传者
时间限制1000ms
内存限制256MiB
通过 / 提交0/0

题目描述

题目译自 Open Olympiad in Informatics 2025 Day2 T3 「Переворот карт / Card Flip」。

彼得和瓦西娅买了一款新的卡片游戏《翻转》。游戏包含 nn 张双面卡片和 mm 张单面卡片:

  1. 双面卡片:正面写有数字 aia_i,背面写有数字 bib_i。
  2. 单面卡片:正面写有一个数字 cic_i。

所有卡片上的数字(包括正反面)均不相同。初始时,所有卡片都正面朝上放在桌面上。在自己的回合中,玩家必须执行以下两种操作之一:

  1. 从桌面上移除写有剩余卡片中最小数字的卡片。
  2. 如果写有最小数字的卡片是双面卡片且当前正面朝上,则可以将其翻转。

赢得游戏的玩家是移除最后一张卡片的人。请确定在彼得先行的情况下,谁将赢得游戏。

输入格式

第一行包含两个整数 nn 和 mm (1≤n,m≤500000)(1 \leq n, m \leq 500000),分别表示双面卡片和单面卡片的数量。

第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_n (1≤ai≤2⋅n+m)(1 \leq a_i \leq 2 \cdot n + m),表示双面卡片正面的数字。

第三行包含 nn 个整数 b1,b2,…,bnb_1, b_2, \ldots, b_n (1≤bi≤2⋅n+m)(1 \leq b_i \leq 2 \cdot n + m),表示双面卡片背面的数字。

第四行包含 mm 个整数 c1,c2,…,cmc_1, c_2, \ldots, c_m (1≤ci≤2⋅n+m)(1 \leq c_i \leq 2 \cdot n + m),表示单面卡片上的数字。

保证从 11 到 2⋅n+m2 \cdot n + m 的每个数字在数组 aa、bb 或 cc 中恰好出现一次。

输出格式

如果彼得赢得游戏,输出 First;如果瓦西娅赢得游戏,输出 Second。

2 1
5 3
1 2
4

First

在第一个样例中,初始时桌面上有卡片 3,4,53, 4, 5。为了获胜,彼得在自己的回合移除卡片 33,之后瓦西娅必须移除卡片 44,因为它是单面卡片。最后,彼得移除卡片 55,此时瓦西娅无卡可移,因此彼得获胜。

1 2
2
3
4 1

Second

在第二个样例中,初始时桌面上有卡片 1,2,41, 2, 4。彼得必须移除卡片 11,因为它是单面卡片。接着,为了获胜,瓦西娅翻转卡片 22,此时桌面上有卡片 33 和 44。彼得必须移除翻转后的卡片 33,之后瓦西娅移除卡片 44。由于卡片已全部移除,瓦西娅获胜。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 00 是样例。

子任务 分值 附加限制 子任务依赖 备注
11 1212 n≤20n \leq 20,m≤10m \leq 10 00
22 1313 n≤20n \leq 20 0,10, 1
33 99 ai>bia_i > b_i
44 1010 max⁡i=1n(ai)<min⁡i=1n(bi)\max_{i=1}^{n}(a_i) < \min_{i=1}^{n}(b_i)
55 66 区间 [min⁡(ai,bi);max⁡(ai,bi)][\min(a_i, b_i); \max(a_i, b_i)] 不相交
66 1111 n≤200n \leq 200,m≤200m \leq 200 区间 [min⁡(ai,bi);max⁡(ai,bi)][\min(a_i, b_i); \max(a_i, b_i)] 嵌套或不相交
77 1414 5,65, 6
88 1313 n≤5000n \leq 5000,m≤5000m \leq 5000 0,1,60, 1, 6
99 1212 0∼80 \sim 8