#D. 醒来(wake)

    Type: RemoteJudge 1000ms 512MiB

醒来(wake)

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

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

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

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

题目描述

赫尔德用一个长为 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 且有解的数据中随机生成。


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

The 2nd Yuzusoft Cup Stage 2: Zhanjiang

Not Attended
Status
Done
Rule
IOI
Problem
6
Start at
2024-3-19 7:30
End at
2024-3-29 7:30
Duration
240 hour(s)
Host
Partic.
10