[THUPC 2023 初赛] 喵了个喵 II

Luogu
IDLGP9139
Time4000ms
Memory1024MB
DifficultyP7
2023Special JudgeO2优化2-SAT可持久化线段树构造THUPC
给定一个长为 $4n$ 的序列,其中 $1\sim n$ 各出现 $4$ 次。问是否能够将其划分为两个相等的子序列。 ## Input 第一行一个正整数 $n$。 第二行 $4n$ 个正整数,表示序列。保证 $1\sim n$ 各出现 $4$ 次。 ## Output 如果不能划分为两个相等的子序列,输出一行 `No`。 否则第一行输出 `Yes`。第二行输出一个长为 $4n$ 的 `01` 串。其中第 $i$ 位表示原序列的第 $i$ 个数被划分到第几个子序列。你需要保证你划分出来的两个子序列完全相等。 [samples] ## Background 本来这题的题面和《喵了个喵》有关的。但是听说有人嫌题面长,就少说点好了。 ## Note #### 样例解释 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:由于考场上数据太弱,本题数据已加强。
Samples
Input #1
2
1 1 2 1 2 2 1 2
Output #1
Yes
10000111
API Response (JSON)
{
  "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$ 的 `...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments