CFCF2146D1.Max Sum OR (Easy Version)

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

这是本题的简单版本。不同之处在于本版本中,l=0l=0,并且 r<2105r<2 \cdot 10^5。只有在你解决了所有版本之后,你才能 hack 别人。

给定两个整数 llrrlrl\le r)。

n=rl+1n = r - l + 1。我们将创建两个数组 aabb,都由 nn 个整数构成。初始时,aabb 都等于 [l,l+1,,r][l, l+1, \ldots, r]。你需要对数组 aa 重新排序,使以下表达式的值最大:

i=1n(ai    bi)\sum_{i=1}^n \left( a_i \;|\; b_i \right)

这里,| 表示按位或运算

你还需要给出一种具体的 aa 的重排方案。

输入格式

每组测试数据包含多组测试用例。第一行为测试用例数 tt1t1041 \le t \le 10^4)。每个测试用例由一行组成,包含两个整数 llrr0=lr<21050 = l \leq r < 2 \cdot 10^5),即 aa 的最小值和最大值。

n=rl+1n = r - l + 1。保证所有测试用例中 nn 的总和不超过 21052 \cdot 10^5

输出格式

对于每个测试用例,输出两行。

第一行为一个整数,表示表达式 i=1n(ai    bi)\sum_{i=1}^n \left( a_i \;|\; b_i \right) 的最大值。

第二行为 nn 个不同的整数 a1,a2,,ana_1, a_2, \ldots, a_n,即重排后的数组 aa

如有多种方案,输出任意一种均可。

输入输出样例

  • 输入#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]a=[3,2,1,0]。表达式的值为 (30)+(21)+(12)+(03)=3+3+3+3=12(3|0)+(2|1)+(1|2)+(0|3)=3+3+3+3=12。可以证明这是该表达式的最大可能值。

第二组测试例中,重排后的数组 a=[7,8,5,4,3,2,9,0,1,6]a=[7,8,5,4,3,2,9,0,1,6]。表达式的值为 9090。可以证明这是该表达式的最大可能值。

首页