codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2119C.md (2517B)


      1 Source: https://codeforces.com/problemset/problem/2119/C
      2 
      3 C. A Good Problem
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 [Juggernaut. - Lost Dream feat.星名はる](https://www.youtube.com/watch?v=TCckJwjMGcc)
     22 
     23 You are given four positive integers $n, l, r, k$. You need to find the lexicographically smallest$^{\text{∗}}$ array $a$ of length $n$, consisting of integers, such that:
     24 
     25 * For every $1 \leq i \leq n$, $l \leq a_i \leq r$.
     26 * $a_1 \, \& \, a_2 \, \& \, \ldots \, \& \, a_n = a_1 \oplus a_2 \oplus \ldots \oplus a_n$, where $\&$ denotes the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND) and $\oplus$ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).
     27 
     28 If no such array exists, output $-1$. Otherwise, since the entire array might be too large to output, output $a_k$ only.
     29 
     30 $^{\text{∗}}$An array $a$ is lexicographically smaller than an array $b$ if and only if one of the following holds:
     31 
     32 * $a$ is a prefix of $b$, but $a \ne b$; or
     33 * in the first position where $a$ and $b$ differ, the array $a$ has a smaller element than the corresponding element in $b$.
     34 
     35 Input
     36 
     37 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     38 
     39 Each test case contains four positive integers $n,l,r,k$ ($1 \le k \le n \le 10^{18}$, $1 \le l \le r \le 10^{18}$).
     40 
     41 Output
     42 
     43 For each test case, output $a_k$ or $-1$ if no array meets the conditions.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 9
     51 
     52 1 4 4 1
     53 
     54 3 1 3 3
     55 
     56 4 6 9 2
     57 
     58 4 6 9 3
     59 
     60 4 6 7 4
     61 
     62 2 5 5 1
     63 
     64 2 3 6 2
     65 
     66 999999999999999999 1000000000000000000 1000000000000000000 999999999999999999
     67 
     68 1000000000000000000 1 999999999999999999 1000000000000000000
     69 ```
     70 
     71 Output
     72 
     73 ```
     74 4
     75 1
     76 6
     77 8
     78 -1
     79 -1
     80 -1
     81 1000000000000000000
     82 2
     83 ```
     84 
     85 Note
     86 
     87 In the first test case, the array $a = [4]$. It can be proven that there is no array that meets the above requirements and has a smaller lexicographic order.
     88 
     89 In the second test case, the array $a= [1,1,1]$. It can be proven that there is no array that meets the above requirements and has a smaller lexicographic order.
     90 
     91 In the third test case and the fourth test case, the array $a = [6,6,8,8]$. It can be proven that there is no array that meets the above requirements and has a smaller lexicographic order.
     92 
     93 In the fifth test case and the sixth test case, it can be proven that there is no array that meets the above requirements.