fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define fore(i,s,e) for (int i = s; i <= e; i++)
  4. #define mod 1000000007
  5. #define pb push_back
  6. #define lb lower_bound
  7. #define ub upper_bound
  8. #define fr first
  9. #define sc second
  10. #define int long long
  11. #define ii pair<int,int>
  12. #define vi vector<int>
  13. #define vii vector<ii>
  14. #define vvi vector<vi>
  15. #define INF 1000000000
  16. #define endl "\n"
  17. #define sort(a) sort(a.begin(),a.end())
  18. #define rev(a) reverse(a.begin(),a.end())
  19. #define debug(x) cout << #x << " " << x << endl;
  20.  
  21. int bc(int n, int k,int md)
  22. {
  23.     if(k<0) return 0;
  24.     int C[n + 1][k + 1];
  25.     int i, j;
  26.     for (i = 0; i <= n; i++) {
  27.         for (j = 0; j <= min(i, k); j++){
  28.             if (j == 0 || j == i)
  29.                 C[i][j] = 1;
  30.             else
  31.               C[i][j] = (C[i - 1][j - 1]%md+ C[i - 1][j]%md)%md;
  32.       }
  33.   }
  34.   return (C[n][k]+md)%md;
  35. }
  36.  
  37. int powb(int x, int y,int md){
  38.     int res=1;
  39.     x=x%md;
  40.     while(y>0){
  41.         if(y%2) res=(res*x)%md;
  42.         y/=2;
  43.         x=(x*x)%md;
  44.     }
  45.     return res;
  46. }
  47.  
  48. int mul(int a,int b)
  49. {
  50.     int res = 0;
  51.     a %= mod;
  52.     while (b)
  53.     {
  54.         if (b & 1)
  55.             res = (res + a) % mod;
  56.         a = (2 * a) % mod;
  57.         b >>= 1;
  58.     }
  59.     return res;
  60. }
  61.  
  62. int gcd(int a,int b)
  63. {
  64.     if(b == 0) return a;
  65.     return gcd(b,a%b);
  66. }
  67.  
  68. template <typename T>
  69. void i_vector(vector<T>&a)
  70. {
  71.     for(int i=0;i<(int)a.size();i++)
  72.         cin>>a[i];
  73. }
  74.  
  75. template <typename T>
  76. void output(vector<T>&a)
  77. {
  78.     for(auto it : a)
  79.         cout<<it<<" ";
  80.     cout<<endl;
  81. }
  82.  
  83. template<typename T>
  84. void output2(vector<vector<T>>& a ){
  85.     if(a.size() == 0) return;
  86.     for(int i=0;i<a.size();i++){
  87.         for(int j=0;j<a[0].size();j++)
  88.             cout<<a[i][j]<<" ";
  89.         cout<<endl;
  90.     }
  91. }
  92.  
  93. const int N = 1e5 + 100;
  94. int a[N];
  95. int n,q,x;
  96. struct trie{
  97.     bool is;
  98.     trie* left;
  99.     trie* right;
  100. };
  101.  
  102. struct trie* get(bool is){
  103.     trie* r = new trie;
  104.     r->left = nullptr;
  105.     r->right = nullptr;
  106.     r->is = is;
  107.     return r;
  108. }
  109.  
  110. void insert(trie* root,int n){
  111.     trie* curr = root;
  112.     while(n){
  113.         int idx = 1 - n%2;
  114.         if(idx == 0){
  115.             if(!curr->left){
  116.                 curr->left = get(false);
  117.             }
  118.             curr = curr->left;
  119.         }
  120.         else{
  121.             if(!curr->right)
  122.                 curr->right = get(false);
  123.             curr = curr->right;
  124.         }
  125.         n/=2;
  126.     }
  127.     curr->is = true;
  128. }
  129.  
  130. bool search(int n,trie* curr){
  131.     if(!n) return true;
  132.     int idx = n%2;
  133.     if(idx == 0 && curr->left){
  134.         if(curr->left->is){
  135.             return true;
  136.         }
  137.         else return search(n/2,curr->left);
  138.     }
  139.     else if(idx == 1 && curr->right){
  140.         if(curr->right->is)
  141.             return true;
  142.         else return search(n/2,curr->right);
  143.     }
  144.     return false;    
  145. }
  146.  
  147. void test_case(int t) 
  148. {
  149.     cin>>n>>q;
  150.     trie* root = get(false);
  151.     for(int i=1;i<=n;i++){
  152.         cin>>a[i];
  153.         insert(root,a[i]);
  154.     }
  155.     while(q--){
  156.         cin>>x;
  157.         cout<<(search(x,root) ? "YES" : "NO")<<endl;
  158.     }
  159. }
  160. int32_t main()
  161. {
  162.     ios::sync_with_stdio(false);
  163.     cin.tie(0);
  164.     #ifndef ONLINE_JUDGE
  165.     freopen("input.txt","r",stdin);
  166.     freopen("output.txt","w",stdout);
  167.     #endif
  168.     int t=0;
  169.     cin>>t;
  170.     for(int i = 1;i<=t;i++)
  171.         test_case(i);
  172.     cerr<<"Time : "<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";
  173. }
Success #stdin #stdout #stderr 0s 5440KB
comments (?)
stdin
copy 
1
5 4
1 2 3 4 5
2 
5 
6 
7
stdout
copy 
YES
YES
YES
NO
stderr
copy 
Time : 4.565ms
https://ideone.com/BRbX1x
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!