codeforces-scrape

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

1842B.md (3098B)


      1 Source: https://codeforces.com/problemset/problem/1842/B
      2 
      3 B. Tenzing and Books
      4 
      5 time limit per test
      6 
      7 1 second
      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 Tenzing received $3n$ books from his fans. The books are arranged in $3$ stacks with $n$ books in each stack. Each book has a non-negative integer difficulty rating.
     22 
     23 Tenzing wants to read some (possibly zero) books. At first, his knowledge is $0$.
     24 
     25 To read the books, Tenzing will choose a non-empty stack, read the book on the top of the stack, and then discard the book. If Tenzing's knowledge is currently $u$, then his knowledge will become $u|v$ after reading a book with difficulty rating $v$. Here $|$ denotes the [bitwise OR operation](https://en.wikipedia.org/wiki/Bitwise_operation#OR). Note that Tenzing can stop reading books whenever he wants.
     26 
     27 Tenzing's favourite number is $x$. Can you help Tenzing check if it is possible for his knowledge to become $x$?
     28 
     29 Input
     30 
     31 Each test contains multiple test cases. The first line of input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of test cases follows.
     32 
     33 The first line of each test case contains two integers $n$ and $x$ ($1 \leq n \leq 10^5$, $0 \leq x \leq 10^9$) — the number of books in each stack and Tenzing's favourite number.
     34 
     35 The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0 \leq a_i \leq 10^9$)  — the difficulty rating of the books in the first stack, from top to bottom.
     36 
     37 The third line of each test case contains $n$ integers $b_1,b_2,\ldots,b_n$ ($0 \leq b_i \leq 10^9$)  — the difficulty rating of the books in the second stack, from top to bottom.
     38 
     39 The fourth line of each test case contains $n$ integers $c_1,c_2,\ldots,c_n$ ($0 \leq c_i \leq 10^9$)  — the difficulty rating of the books in the third stack, from top to bottom.
     40 
     41 It is guaranteed that the sum of $n$ does not exceed $10^5$.
     42 
     43 Output
     44 
     45 For each test case, output "Yes" (without quotes) if Tenzing can make his knowledge equal to $x$, and "No" (without quotes) otherwise.
     46 
     47 You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 3
     55 
     56 5 7
     57 
     58 1 2 3 4 5
     59 
     60 5 4 3 2 1
     61 
     62 1 3 5 7 9
     63 
     64 5 2
     65 
     66 3 2 3 4 5
     67 
     68 5 4 3 2 1
     69 
     70 3 3 5 7 9
     71 
     72 3 0
     73 
     74 1 2 3
     75 
     76 3 2 1
     77 
     78 2 2 2
     79 ```
     80 
     81 Output
     82 
     83 ```
     84 Yes
     85 No
     86 Yes
     87 ```
     88 
     89 Note
     90 
     91 For the first test case, Tenzing can read the following $4$ books:
     92 
     93 * read the book with difficulty rating $1$ on the top of the first stack. Tenzing's knowledge changes to $0|1=1$.
     94 * read the book with difficulty rating $1$ on the top of the third stack. Tenzing's knowledge changes to $1|1=1$.
     95 * read the book with difficulty rating $2$ on the top of the first stack. Tenzing's knowledge changes to $1|2=3$.
     96 * read the book with difficulty rating $5$ on the top of the second stack. Tenzing's knowledge changes to $3|5=7$.
     97 
     98 After reading all books, Tenzing's knowledge is $7$.
     99 
    100 For the third test case, Tenzing can read $0$ books to make his final knowledge equals to $0$.