#P8553. 醒来

    ID: 7993 Type: RemoteJudge 1000ms 512MiB Tried: 0 Accepted: 0 Difficulty: 7 Uploaded By: Tags>递归洛谷原创Special JudgeO2优化分治构造洛谷月赛

醒来

题目背景

“那羡慕的烟火去哪了,那信任的朋友疏远了。

我年幼时坚持过什么,你们还记不记得。”

回想自己儿时的样子,已和现在大不相同了;但想想昨天的自己,却与今天没什么差异。这不经意的改变,让我们已经是另一个样子了。

题目描述

赫尔德用一个长为 rl+1r-l+1 的数列 aa 来描述自己性格的变化。但赫尔德记忆不好,她已经记不清 aa 了,只记得非负整数 l,rl,r,其中 l<rl<r

不过,她还记得:

  1. lairl\le a_i\le r,且 aia_i 互不相同。换言之,aa 是一个 lrl\sim r 的排列。
  2. 对于所有 1irl1\le i\le r-l,有 $\operatorname{popcount}(a_i \mathbin{\mathrm{xor}} a_{i+1})=1$。换言之,aa 中相邻的两个数二进制下只相差一位。

请你告诉她一个可能的 aa,或告诉她其实不存在这样的 aa

输入格式

仅一行,两个非负整数 l,rl,r

输出格式

第一行,若有解输出 Yes,若无解则输出 No。不区分大小写。

若你输出了 Yes,则你可以用以下两种格式之一输出你的构造:

  1. 输出一行 rl+1r-l+1 个数,表示你构造的排列。
  2. 先输出一个数,表示你构造排列的第一个数。接下来输出一个长为 rlr-l 的字符串,对于第 ii 个字符,若你构造排列第 iii+1i+1 个数相差了 2k2^k,则你应该输出第 k+1k+1 个小写英文字母,即 (char)('a'+k)

注意,若你使用格式 1 输出,你可能无法通过最后两个子任务。若您获得了 UKE 的评测结果,请考虑修改输出答案的格式。


【评分方法】

本题采用自定义校验器检测你的输出。

若你对解的存在性判断错误,你无法获得任何分数。

若你对解的存在性判断正确,你可以获得 40%40\% 的分数;若解不存在或你给出了一组正确的构造,则你可以获得剩下 60%60\% 的分数。

0 7

Yes
0 1 3 2 6 7 5 4

0 7

yEs
0 abacaba

0 7

yes

3 5

No

提示

【样例解释 #1、#2、#3】

样例输出 #1 和 #2 对应同一个数列,即 {0,1,3,2,6,7,5,4}\{ 0, 1, 3, 2, 6, 7, 5, 4 \},它们均能获得该测试点 100%100 \% 的分数。

样例输出 #3 能获得该测试点 40%40 \% 的分数。


【数据范围】

对于所有数据,保证 0l<r1070\le l<r\le 10^7

n=rl+1n=r-l+1

$$\def{\arraystretch}{1.5} \begin{array}{c|c|c|c}\hline \textbf{子任务编号}&\bm{~~~~~~~~n\le~~~~~~~~}&~~~~\textbf{特殊限制}~~~~&\textbf{分数}\cr\hline \textsf1 & 10& &9\cr\hline \textsf2 & 20& &9 \cr\hline \textsf3 & 10^5&\textsf{A, B}&10\cr\hline \textsf4 & 10^5 &\sf A&10\cr\hline \textsf5 & 2000& \textsf C&25 \cr\hline \textsf6 & 5\times 10^5&\textsf D&20\cr\hline \textsf7 & 3\times 10^6&&10\cr\hline \textsf8 & &&7\cr\hline \end{array} $$

A\textsf A:保证 l=0l=0

B\textsf B:保证 nn22 的整数次幂。

C\textsf C:保证 ll 是偶数,rr 是奇数。

D\textsf D:本子任务有 5 个测试点,从所有 n2×105n\ge 2\times 10^5 且有解的数据中随机生成。


即使一直在改变,赫尔德也许仍似儿时的自己。