{"problem":{"name":"[THUPC 2023 初赛] 喵了个喵 II","description":{"content":"给定一个长为 $4n$ 的序列，其中 $1\\sim n$ 各出现 $4$ 次。问是否能够将其划分为两个相等的子序列。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":4000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9139"},"statements":[{"statement_type":"Markdown","content":"给定一个长为 $4n$ 的序列，其中 $1\\sim n$ 各出现 $4$ 次。问是否能够将其划分为两个相等的子序列。\n\n## Input\n\n第一行一个正整数 $n$。\n\n第二行 $4n$ 个正整数，表示序列。保证 $1\\sim n$ 各出现 $4$ 次。\n\n## Output\n\n如果不能划分为两个相等的子序列，输出一行 `No`。\n\n否则第一行输出 `Yes`。第二行输出一个长为 $4n$ 的 `01` 串。其中第 $i$ 位表示原序列的第 $i$ 个数被划分到第几个子序列。你需要保证你划分出来的两个子序列完全相等。\n\n[samples]\n\n## Background\n\n本来这题的题面和《喵了个喵》有关的。但是听说有人嫌题面长，就少说点好了。\n\n## Note\n\n#### 样例解释 1\n\n两个子序列均为 $(1,2,1,2)$。\n\n#### 子任务\n\n保证 $1\\le n \\le 5\\times10^4$。\n\n保证序列中 $1\\sim n$ 各出现 $4$ 次。\n\n#### 评分方式\n\n你的输出的第一行需要与标准答案一致。若为 `Yes`，输出任意一种合法的划分均算正确。\n\n#### 题目来源\n\n来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）初赛。\n\n题解等资源可在 <https://github.com/THUSAAC/THUPC2023-Pre> 查看。\n\nBy E.Space：由于考场上数据太弱，本题数据已加强。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9139","tags":["2023","Special Judge","O2优化","2-SAT","可持久化线段树","构造","THUPC"],"sample_group":[["2\n1 1 2 1 2 2 1 2","Yes\n10000111\n"]],"created_at":"2026-03-03 11:09:25"}}