题目名称 3983. 艾姆易艾克斯
输入输出 Mex.in/out
难度等级
时间限制 1000 ms (1 s)
内存限制 512 MiB
测试数据 20
题目来源 Gravatarop_组撒头屯 于2024-06-28加入
开放分组 全部用户
提交状态
分类标签
分享题解
通过:12, 提交:40, 通过率:30%
Gravatar2_16鸡扒拌面 100 0.079 s 1.45 MiB C++
Gravatarwdsjl 100 0.113 s 1.38 MiB C++
Gravatarop_组撒头屯 100 0.119 s 2.12 MiB C++
GravatarAeeE5x 100 0.143 s 1.30 MiB C++
Gravatarqyd 100 0.215 s 3.73 MiB C++
Gravatar┭┮﹏┭┮ 100 0.216 s 2.86 MiB C++
Gravatar彭欣越 100 0.221 s 2.06 MiB C++
Gravatar小金 100 0.240 s 1.51 MiB C++
Gravatar健康铀 100 0.265 s 1.60 MiB C++
Gravatarflyfree 100 0.271 s 2.67 MiB C++
本题关联比赛
2024暑期C班集训1
关于 艾姆易艾克斯 的近10条评论(全部评论)

3983. 艾姆易艾克斯

★   输入文件:Mex.in   输出文件:Mex.out   简单对比
时间限制:1 s   内存限制:512 MiB

【题目描述】

设 $A$ 是非负整数序列,定义 $Mex(A)$ 为序列 $A$ 中没有出现的最小的非负整数。比如 $Mex(0, 1, 3, 3, 2) = 4$, $Mex(5, 0, 0, 1, 4) = 2$。

给定长度为 $n$ 的两个序列 $A$ 和 $B$,对于每个位置 $i(1 ≤ i ≤ n)$ 你可以选择交换 $A_i$ 和 $B_i$ 或者不交换,现在你希望最终的 $Mex(A)$ 尽可能小,请求出这个最小值,以及满足这个最小值的方案数对 $10^9 + 7$ 取模的结果。

【输入格式】

第一行一个正整数 $n$。

第二行 $n$ 个非负整数 $A_1, ..., A_n$。

第三行 $n$ 个非负整数 $B_1, ..., B_n$。

【输出格式】

输出两个整数,分别表示最小的 $Mex(A)$ 和方案数对 $10^9 + 7$ 取模的结果。

【样例输入1】

2
0 1
1 1

【样例输出1】

0 2

【样例说明1】

容易发现必须交换 $A_1$ 和 $B_1$,$A_2, B_2$ 可以选择交换或者不交换,最终的 $Mex(A)$ 为 $Mex(1, 1) = 0$。

【样例输入2】

4
0 1 2 3
0 1 2 3

【样例输出2】

4 16

【数据规模与约定】

大样例

对于 $100\%$ 的数据 $1 \le n\le 10^5, 0\le A_i,B_i \le 10^9$。

·$Subtask1(30pts): n\le 15$。

·$Subtask2(20pts): n\le 2000, A_i=B_i$。

·$Subtask3(30pts): n\le 2000$。

·$Subtask4(20pts): 无特殊限制$。

【来源】

在此键入。