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.
Tenzing wants to read some (possibly zero) books. At first, his knowledge is 0 .
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. Note that Tenzing can stop reading books whenever he wants.
Tenzing's favourite number is x . Can you help Tenzing check if it is possible for his knowledge to become x ?
Input Each test contains multiple test cases. The first line of input contains a single integer t (1≤t≤10^4 ) — the number of test cases. The description of test cases follows.
The first line of each test case contains two integers n and x (1≤n≤10^5 , 0≤x≤10^9 ) — the number of books in each stack and Tenzing's favourite number.
The second line of each test case contains n integers a1,a2,…,an (0≤ai≤10^9 ) — the difficulty rating of the books in the first stack, from top to bottom.
The third line of each test case contains n integers b1,b2,…,bn (0≤bi≤10^9 ) — the difficulty rating of the books in the second stack, from top to bottom.
The fourth line of each test case contains n integers c1,c2,…,cn (0≤ci≤10^9 ) — the difficulty rating of the books in the third stack, from top to bottom.
It is guaranteed that the sum of n does not exceed 10^5 .
Output For each test case, output "Yes" (without quotes) if Tenzing can make his knowledge equal to x , and "No" (without quotes) otherwise.
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.
This was the question needed to be solved.
This is the code that I was able to come up with during the round, but the output was wrong answer on test case 2. The review sadly doesn't show what the exact test case is, so I haven't been able to get the exact test case, and try to deduce the mistake based on that.
#include <iostream>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n,i,p1=0,p2=0,p3=0;
long long x,knowledge=0;
cin>>n>>x;
long long a[n],b[n],c[n];
for(i=0;i<n;i++)
cin>>a[i];
for(i=0;i<n;i++)
cin>>b[i];
for(i=0;i<n;i++)
cin>>c[i];
while(p1<n||p2<n||p3<n)
{
if(knowledge==x)
{
cout<<"YES"<<endl;
break;
}
if(knowledge > x)
{
cout<<"NO"<<endl;
break;
}
if(p1<n && (a[p1]|x)==x)
knowledge |= a[p1++];
else if(p2<n && (b[p2]|x)==x)
knowledge |= b[p2++];
else if(p3<n && (c[p3]|x)==x)
knowledge |= c[p3++];
else
{
cout<<"NO"<<endl;
break;
}
}
if(p1>=n&&p2>=n&&p3>=n)
cout<<"NO"<<endl;
}
return 0;
}
I've also tried to test different test cases by myself but haven't seen one where the it would fail. Any help is appreciated :)
Your approach is sound, but there is a bug, finding which given a test case I leave as an exercise.
1
1 7
1
2
4
Expected output: YES. Actual output: NO.