[THUPC 2023 初赛] 喵了个喵 II
题目背景
本来这题的题面和《喵了个喵》有关的。但是听说有人嫌题面长,就少说点好了。
题目描述
给定一个长为 $4n$ 的序列,其中 $1\sim n$ 各出现 $4$ 次。问是否能够将其划分为两个相等的子序列。
输入输出格式
输入格式
第一行一个正整数 $n$。
第二行 $4n$ 个正整数,表示序列。保证 $1\sim n$ 各出现 $4$ 次。
输出格式
如果不能划分为两个相等的子序列,输出一行 `No`。
否则第一行输出 `Yes`。第二行输出一个长为 $4n$ 的 `01` 串。其中第 $i$ 位表示原序列的第 $i$ 个数被划分到第几个子序列。你需要保证你划分出来的两个子序列完全相等。
输入输出样例
输入样例 #1
2
1 1 2 1 2 2 1 2
输出样例 #1
Yes
10000111
说明
#### 样例解释 1
两个子序列均为 $(1,2,1,2)$。
#### 子任务
保证 $1\le n \le 5\times10^4$。
保证序列中 $1\sim n$ 各出现 $4$ 次。
#### 评分方式
你的输出的第一行需要与标准答案一致。若为 `Yes`,输出任意一种合法的划分均算正确。
#### 题目来源
来自 2023 清华大学学生程序设计竞赛暨高校邀请赛(THUPC2023)初赛。
题解等资源可在 <https://github.com/THUSAAC/THUPC2023-Pre> 查看。
By E.Space:由于考场上数据太弱,我于 3.12 和 3.19 两度加强了数据。