/ 
実行時間制限: 4 sec / メモリ制限: 1024 MiB
配点 : 800 点
問題文
非負整数 q,L,R\;(q \in \{ 0,1\}, \; L \leq R) が与えられます。 以下のすべての条件を満たす集合 S について考えます。
- S は L 以上 R 以下の互いに相異なる整数からなる。
- a \in S, \; b \in S, \; a \neq b のとき、a と b は 2 進表記で 2 桁以上異なる。 より厳密には、\left\lfloor\frac{a}{2^i}\right\rfloor と \left\lfloor\frac{b}{2^i}\right\rfloor の偶奇が異なるような非負整数 i が 2 個以上存在する。
- 上の 2 条件を満たすもののうち、要素数が最大となる。
q=0 のとき、このような集合 S の要素数を求めてください。
q=1 のとき、このような集合 S を一つ構築してください。
1 つの入力ファイルにつき、T 個のテストケースを解いてください。
制約
- 1 \leq T \leq 2 \times 10^5
- 0 \leq q \leq 1
- 0 \leq L \leq R \leq 10^{18}
- 全てのテストケースにおける q(R-L) の総和は 5\times 10^6 以下
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
T case_1 case_2 \vdots case_T
各ケースは以下の形式で与えられる。
q L R
出力
答えを合計 T 行で出力せよ。
t 個目のテストケースの答えを t 行目に出力せよ。
各テストケースでは、q=0 ならば条件を満たす集合 S の要素数を出力せよ。
q=1 ならば条件を満たすような集合 S に対して
B_i=\begin{cases} 1 \; (S \text{ に } i \text{ が含まれる }) \\ 0 \; (S \text{ に } i \text{ が含まれない }) \end{cases}
として、以下の形式で出力せよ。
B_LB_{L+1}\dotsB_R
条件を満たす S が複数存在する場合はどれを出力してもよい。
入力例 1
3 1 0 3 0 1 2 1 213 213
出力例 1
1001 2 1
1 つ目のテストケースでは、S=\{0,3\} は条件を満たします。
S=\{1,2\} も条件を満たすため正解となります。
2 つ目のテストケースでは、条件を満たす S は \{1,2\} のみで、その要素数は 2 です。
Score : 800 points
Problem Statement
You are given non-negative integers q,L,R\;(q \in \{ 0,1\}, \; L \leq R). Consider a set S that satisfies all of the following conditions.
- S consists of distinct integers between L and R, inclusive.
- If a \in S, \; b \in S, \; a \neq b, then a and b differ in at least two digits in binary representation. More formally, there exist at least two non-negative integers i such that \left\lfloor\frac{a}{2^i}\right\rfloor and \left\lfloor\frac{b}{2^i}\right\rfloor have different parities.
- Among those satisfying the above two conditions, the number of elements is maximum.
If q=0, find the number of elements in such a set S.
If q=1, construct one such set S.
For each input file, solve T test cases.
Constraints
- 1 \leq T \leq 2 \times 10^5
- 0 \leq q \leq 1
- 0 \leq L \leq R \leq 10^{18}
- The sum of q(R-L) over all test cases is at most 5\times 10^6.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T case_1 case_2 \vdots case_T
Each case is given in the following format:
q L R
Output
Output the answers in a total of T lines.
The t-th line should contain the answer for the t-th test case.
For each test case, if q=0, print the number of elements in a set S that satisfies the conditions.
If q=1, for a set S that satisfies the conditions, let
B_i=\begin{cases} 1 \; (S \text{ contains } i) \\ 0 \; (S \text{ does not contain } i) \end{cases}
and output it in the following format:
B_LB_{L+1}\dotsB_R
If there are multiple sets S that satisfy the conditions, you may print any of them.
Sample Input 1
3 1 0 3 0 1 2 1 213 213
Sample Output 1
1001 2 1
In the first test case, S=\{0,3\} satisfies the conditions.
S=\{1,2\} also satisfies the conditions, so it is correct as well.
In the second test case, the only S that satisfies the conditions is \{1,2\}, whose number of elements is 2.