fork(1) download
copy 
  1.  #include<iostream>
  2. #include<string>
  3. #include<algorithm>
  4. #include<stack>
  5. #include<math.h>
  6. #include<map>
  7. #include <unordered_map> 
  8. #include<vector>
  9. #include<queue>
  10. #include<set>
  11. #include <bits/stdc++.h>
  12. #include<deque> 
  13. #include<string>
  14. #define N 40
  15. #define K 100005
  16. #define MOD 1e9+7
  17. #define ll long long int
  18. using namespace std;
  19.  
  20. ll max(ll a, ll b){
  21.     if(a>b)
  22.         return a;
  23.     return b;
  24. }
  25. ll min(ll a, ll b){
  26.     if(a<b)
  27.         return a;
  28.     return b;
  29. }
  30.  
  31. const int ALPHABET_SIZE = 2;
  32.  
  33. struct TrieNode 
  34. { 
  35.     struct TrieNode *children[ALPHABET_SIZE]; 
  36.  
  37.     // isEndOfWord is true if the node represents 
  38.     // end of a word 
  39.     int index_of_no; 
  40. }; 
  41.  
  42. struct TrieNode *getNode(void) 
  43. { 
  44.     struct TrieNode *pNode =  new TrieNode; 
  45.  
  46.     pNode->index_of_no = 0; 
  47.  
  48.     for (int i = 0; i < ALPHABET_SIZE; i++) 
  49.         pNode->children[i] = NULL; 
  50.  
  51.     return pNode; 
  52. }
  53.  
  54. void insert(struct TrieNode *root, string key, int pos) 
  55. { 
  56.     struct TrieNode *pCrawl = root; 
  57.  
  58.     for (int i = 0; i < key.length(); i++) 
  59.     { 
  60.         int index = key[i] - '0'; 
  61.         if (!pCrawl->children[index]) 
  62.             pCrawl->children[index] = getNode(); 
  63.  
  64.         pCrawl = pCrawl->children[index]; 
  65.     } 
  66.  
  67.     // mark last node as leaf 
  68.     pCrawl->index_of_no = pos; 
  69. }
  70.  
  71. string get_32_bit(int val){
  72.     int lim = 32;
  73.     char bin[lim+1];
  74.     bin[lim] = '\0';
  75.     for(int i=0;i<lim;i++){
  76.         bin[i] = '0';
  77.     }
  78.     int i = 0;
  79.     while(val >0){
  80.         int rem = val%2;
  81.         bin[lim-1-i] = rem + '0';
  82.         i++;
  83.         val/=2;
  84.     }
  85.  
  86.     return bin;
  87. }
  88.  
  89. int search(struct TrieNode *root, string key) 
  90. { 
  91.     struct TrieNode *pCrawl = root; 
  92.     //cout<<key.length()<<endl;
  93.     for (int i = 0; i < key.length(); i++) 
  94.     { 
  95.         int index = key[i] - '0';
  96.         if(!pCrawl->children[index]){
  97.             if(pCrawl->children[0] != NULL){
  98.  
  99.                 pCrawl = pCrawl->children[0];
  100.                 //cout<<i<<" 00"<<endl;
  101.             }
  102.             else if(pCrawl->children[1] != NULL){
  103.                 pCrawl = pCrawl->children[1];
  104.                 //cout<<i<<" 11"<<endl;
  105.             }
  106.             /*
  107.             else{
  108.                 cout<<i<<" return from here"<<endl;
  109.                 return pCrawl->index_of_no;
  110.             }*/
  111.         }
  112.         else{
  113.             pCrawl = pCrawl->children[index];
  114.             //cout<<i<<" match"<<endl;
  115.         }
  116.  
  117.     } 
  118.     return pCrawl->index_of_no;
  119.  
  120. } 
  121.  
  122. string comple(string s){
  123.     char inv[33];
  124.     for(int i=0;i<s.length();i++){
  125.         if(s[i] == '0')
  126.             inv[i] = '1';
  127.         else
  128.             inv[i] = '0';
  129.     }
  130.     inv[32] = '\0';
  131.     return inv;
  132. }
  133.  
  134. int main(){
  135.     int t;
  136.     cin>>t;
  137.     while(t--){
  138.         int n, q;
  139.         cin>>n>>q;
  140.         int x[q];
  141.         int nos[n];
  142.         for(int i=0;i<n;i++){
  143.             cin>>nos[i];
  144.         }
  145.         for(int i=0;i<q;i++){
  146.             cin>>x[i];
  147.         }
  148.         struct TrieNode *root = getNode();
  149.         for(int i=0;i<n;i++){
  150.             int val = nos[i];
  151.             string s = get_32_bit(val);
  152.             //cout<<i<<" "<<s<<endl;
  153.             insert(root, s, i+1);
  154.         }
  155.  
  156.         string req;
  157.         for(int i=0;i<q;i++){
  158.             string pres = get_32_bit(x[i]);
  159.  
  160.             string req = comple(pres);
  161.             //cout<<"$ "<<req<<endl;
  162.             int matching_pos = search(root, req);
  163.             cout<<matching_pos<<endl;
  164.  
  165.         }
  166.     }
  167.  
  168.  
  169.  
  170.  
  171. }
Success #stdin #stdout 0s 4476KB
comments (?)
stdin
copy 
1
3 3
3 1 2
4
5
6
stdout
copy 
1
3
2
https://ideone.com/EamMC8
1
3 3
3 1 2
4
5
6
language:
C++14 (gcc 8.3)
created:
4 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!