Hamming Distance is not 1

AtCoder

IDarc213_b

Time4000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

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$.

API Response (JSON)

{
  "problem": {
    "name": "Hamming Distance is not 1",
    "description": {
      "content": "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$,",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc213_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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.\n\n*   $S$ consists of distinct integers between $L$ and $R$,...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments