fork 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.     if(pCrawl->index_of_no!= 0){
  69.     	pCrawl->index_of_no = min(pCrawl->index_of_no, pos);
  70.     } 
  71.     else
  72.     	pCrawl->index_of_no = pos; 
  73. }
  74.  
  75. string get_32_bit(int val){
  76.     int lim = 32;
  77.     char bin[lim+1];
  78.     bin[lim] = '\0';
  79.     for(int i=0;i<lim;i++){
  80.         bin[i] = '0';
  81.     }
  82.     int i = 0;
  83.     while(val >0){
  84.         int rem = val%2;
  85.         bin[lim-1-i] = rem + '0';
  86.         i++;
  87.         val/=2;
  88.     }
  89.  
  90.     return bin;
  91. }
  92.  
  93. int search(struct TrieNode *root, string key) 
  94. { 
  95.     struct TrieNode *pCrawl = root; 
  96.     //cout<<key.length()<<endl;
  97.     for (int i = 0; i < key.length(); i++) 
  98.     { 
  99.         int index = key[i] - '0';
  100.         if(!pCrawl->children[index]){
  101.             if(pCrawl->children[0] != NULL){
  102.  
  103.                 pCrawl = pCrawl->children[0];
  104.                 //cout<<i<<" 00"<<endl;
  105.             }
  106.             else if(pCrawl->children[1] != NULL){
  107.                 pCrawl = pCrawl->children[1];
  108.                 //cout<<i<<" 11"<<endl;
  109.             }
  110.             /*
  111.             else{
  112.                 cout<<i<<" return from here"<<endl;
  113.                 return pCrawl->index_of_no;
  114.             }*/
  115.         }
  116.         else{
  117.             pCrawl = pCrawl->children[index];
  118.             //cout<<i<<" match"<<endl;
  119.         }
  120.  
  121.     } 
  122.     return pCrawl->index_of_no;
  123.  
  124. } 
  125.  
  126. string comple(string s){
  127.     char inv[33];
  128.     for(int i=0;i<s.length();i++){
  129.         if(s[i] == '0')
  130.             inv[i] = '1';
  131.         else
  132.             inv[i] = '0';
  133.     }
  134.     inv[32] = '\0';
  135.     return inv;
  136. }
  137.  
  138. int main(){
  139.     ios_base::sync_with_stdio(false);
  140.     cin.tie(NULL);
  141.     int t;
  142.     cin>>t;
  143.     while(t--){
  144.         int n, q;
  145.         cin>>n>>q;
  146.         int x[q];
  147.         int nos[n];
  148.         for(int i=0;i<n;i++){
  149.             cin>>nos[i];
  150.         }
  151.         for(int i=0;i<q;i++){
  152.             cin>>x[i];
  153.         }
  154.         struct TrieNode *root = getNode();
  155.         for(int i=0;i<n;i++){
  156.             int val = nos[i];
  157.             string s = get_32_bit(val);
  158.             //cout<<i<<" "<<s<<endl;
  159.             insert(root, s, i+1);
  160.         }
  161.  
  162.         string req;
  163.         for(int i=0;i<q;i++){
  164.             string pres = get_32_bit(x[i]);
  165.  
  166.             string req = comple(pres);
  167.             //cout<<"$ "<<req<<endl;
  168.             int matching_pos = search(root, req);
  169.             cout<<matching_pos<<endl;
  170.  
  171.         }
  172.     }
  173.  
  174.  
  175.  
  176.  
  177. }
Runtime error #stdin #stdout 0s 4232KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/VqZDgb
1
2 1
38 38
3
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!