CFCF2146D1.Max Sum OR (Easy Version)
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
这是本题的简单版本。不同之处在于本版本中,l=0,并且 r<2⋅105。只有在你解决了所有版本之后,你才能 hack 别人。
给定两个整数 l 和 r(l≤r)。
令 n=r−l+1。我们将创建两个数组 a 和 b,都由 n 个整数构成。初始时,a 和 b 都等于 [l,l+1,…,r]。你需要对数组 a 重新排序,使以下表达式的值最大:
i=1∑n(ai∣bi)
这里,∣ 表示按位或运算。
你还需要给出一种具体的 a 的重排方案。
输入格式
每组测试数据包含多组测试用例。第一行为测试用例数 t(1≤t≤104)。每个测试用例由一行组成,包含两个整数 l 和 r(0=l≤r<2⋅105),即 a 的最小值和最大值。
令 n=r−l+1。保证所有测试用例中 n 的总和不超过 2⋅105。
输出格式
对于每个测试用例,输出两行。
第一行为一个整数,表示表达式 ∑i=1n(ai∣bi) 的最大值。
第二行为 n 个不同的整数 a1,a2,…,an,即重排后的数组 a。
如有多种方案,输出任意一种均可。
输入输出样例
输入#1
3 0 3 0 9 0 15
输出#1
12 3 2 1 0 90 7 8 5 4 3 2 9 0 1 6 240 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
说明/提示
第一组测试例中,重排后的数组 a=[3,2,1,0]。表达式的值为 (3∣0)+(2∣1)+(1∣2)+(0∣3)=3+3+3+3=12。可以证明这是该表达式的最大可能值。
第二组测试例中,重排后的数组 a=[7,8,5,4,3,2,9,0,1,6]。表达式的值为 90。可以证明这是该表达式的最大可能值。