醒来

Luogu
IDLGP8553
Time1000ms
Memory512MB
DifficultyP7
递归洛谷原创Special JudgeO2优化分治构造洛谷月赛
赫尔德用一个长为 $r-l+1$ 的数列 $a$ 来描述自己性格的变化。但赫尔德记忆不好,她已经记不清 $a$ 了,只记得非负整数 $l,r$,其中 $l<r$。 不过,她还记得: 1. $l\le a_i\le r$,且 $a_i$ 互不相同。换言之,$a$ 是一个 $l\sim r$ 的排列。 2. 对于所有 $1\le i\le r-l$,有 $\operatorname{popcount}(a_i \mathbin{\mathrm{xor}} a_{i+1})=1$。换言之,$a$ 中相邻的两个数二进制下只相差一位。 请你告诉她一个可能的 $a$,或告诉她其实不存在这样的 $a$。 ## Input 仅一行,两个非负整数 $l,r$。 ## Output 第一行,若有解输出 `Yes`,若无解则输出 `No`。不区分大小写。 若你输出了 `Yes`,则你可以用以下两种格式之一输出你的构造: 1. 输出一行 $r-l+1$ 个数,表示你构造的排列。 3. 先输出一个数,表示你构造排列的第一个数。接下来输出一个长为 $r-l$ 的字符串,对于第 $i$ 个字符,若你构造排列第 $i$ 与 $i+1$ 个数相差了 $2^k$,则你应该输出第 $k+1$ 个小写英文字母,即 `(char)('a'+k)`。 **注意,若你使用格式 1 输出,你可能无法通过最后两个子任务。若您获得了 UKE 的评测结果,请考虑修改输出答案的格式。** --- **【评分方法】** 本题采用**自定义校验器**检测你的输出。 若你对解的存在性判断错误,你无法获得任何分数。 若你对解的存在性判断正确,你可以获得 $40\%$ 的分数;若解不存在或你给出了一组正确的构造,则你可以获得剩下 $60\%$ 的分数。 [samples] ## Background “那羡慕的烟火去哪了,那信任的朋友疏远了。 我年幼时坚持过什么,你们还记不记得。” 回想自己儿时的样子,已和现在大不相同了;但想想昨天的自己,却与今天没什么差异。这不经意的改变,让我们已经是另一个样子了。 ## Note **【样例解释 \#1、\#2、\#3】** 样例输出 \#1 和 \#2 对应同一个数列,即 $\{ 0, 1, 3, 2, 6, 7, 5, 4 \}$,它们均能获得该测试点 $100 \%$ 的分数。 样例输出 \#3 能获得该测试点 $40 \%$ 的分数。 ---- **【数据范围】** 对于所有数据,保证 $0\le l<r\le 10^7$。 设 $n=r-l+1$。 | 子任务编号 | $ n \leq $ | 特殊限制 | 分数 | |:---:|:---:|:---:|:---:| | $1$ | $ 10 $ | — | $ 9 $ | | $2$ | $ 20 $ | — | $ 9 $ | | $3$ | $ 10^5 $ | $\textsf{A, B}$ | $ 10 $ | | $4$ | $ 10^5 $ | $\textsf{A}$ | $ 10 $ | | $5$ | $ 2000 $ | $\textsf{C}$ | $ 25 $ | | $6$ | $ 5 \times 10^5 $ | $\textsf{D}$ | $ 20 $ | | $7$ | $ 3 \times 10^6 $ | — | $ 10 $ | | $8$ | — | — | $ 7 $ | $\textsf A$:保证 $l=0$。 $\textsf B$:保证 $n$ 是 $2$ 的整数次幂。 $\textsf C$:保证 $l$ 是偶数,$r$ 是奇数。 $\textsf D$:本子任务有 5 个测试点,从所有 $n\ge 2\times 10^5$ 且有解的数据中随机生成。 --- 即使一直在改变,赫尔德也许仍似儿时的自己。
Samples
Input #1
0 7
Output #1
Yes
0 1 3 2 6 7 5 4
Input #2
0 7
Output #2
yEs
0 abacaba
Input #3
0 7
Output #3
yes
Input #4
3 5
Output #4
No
API Response (JSON)
{
  "problem": {
    "name": "醒来",
    "description": {
      "content": "赫尔德用一个长为 $r-l+1$ 的数列 $a$ 来描述自己性格的变化。但赫尔德记忆不好,她已经记不清 $a$ 了,只记得非负整数 $l,r$,其中 $l<r$。 不过,她还记得: 1.  $l\\le a_i\\le r$,且 $a_i$ 互不相同。换言之,$a$ 是一个 $l\\sim r$ 的排列。 2.  对于所有 $1\\le i\\le r-l$,有 $\\operatorname{popco",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8553"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "赫尔德用一个长为 $r-l+1$ 的数列 $a$ 来描述自己性格的变化。但赫尔德记忆不好,她已经记不清 $a$ 了,只记得非负整数 $l,r$,其中 $l<r$。\n\n不过,她还记得:\n\n1.  $l\\le a_i\\le r$,且 $a_i$ 互不相同。换言之,$a$ 是一个 $l\\sim r$ 的排列。\n2.  对于所有 $1\\le i\\le r-l$,有 $\\operatorname{popco...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments