fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct node
  5. {
  6.     long long data;
  7.     node *child[2];
  8. };
  9. node *newNode(long long d)
  10. {
  11.     node *root = new node;
  12.     root->data = d;
  13.     root->child[0] = NULL;
  14.     root->child[1] = NULL;
  15.     return root;
  16. }
  17. void insert(node *root,long long num)
  18. {
  19.     node *curr = root;
  20.  
  21.     for(int i=61;i>=0;i--)
  22.     {
  23.         bool bit = (num & (1<<i));
  24.  
  25.         if(curr->child[bit]==NULL)
  26.         curr->child[bit] = newNode(num);
  27.  
  28.         curr = curr->child[bit];
  29.     }
  30. }
  31.  
  32. long long search(node *root,long long num,int depth)
  33. {
  34.     if(root==NULL)
  35.         return INT_MAX;
  36.  
  37.     if(root->child[0]==NULL&&root->child[1]==NULL)
  38.     return ((root->data)&(num));
  39.  
  40.     bool bit = (num & (1<<depth));
  41.  
  42.     if(bit)
  43.     {
  44.        if(root->child[0]!=NULL)
  45.        return search(root->child[0],num,depth-1);
  46.        else
  47.        return search(root->child[1],num,depth-1);
  48.     }
  49.  
  50.     return min(search(root->child[0],num,depth-1),search(root->child[1],num,depth-1));
  51. }
  52.  
  53. void del(node *root)
  54. {
  55.     if(root==NULL)
  56.     return;
  57.  
  58.     if(root->child[0]==NULL&&root->child[1]==NULL)
  59.     {
  60.         delete(root);
  61.         return;
  62.     }
  63.  
  64.     del(root->child[0]);
  65.     del(root->child[1]);
  66.  
  67.     delete(root);
  68. }
  69.  
  70.  
  71. int main()
  72. {
  73.     int t,n,k;
  74.  
  75.     scanf("%d",&t);
  76.  
  77.     for(int l=1;l<=t;l++)
  78.     {
  79.         node *root = newNode(0);
  80.  
  81.         scanf("%d%d",&n,&k);
  82.  
  83.         long long num[n+1];
  84.  
  85.         for(int i=0;i<n;i++)
  86.         {
  87.             scanf("%lld",&num[i]);
  88.             insert(root,num[i]);
  89.         }
  90.  
  91.         long long mx = 0;
  92.  
  93.         for(int i=0;i<n;i++)
  94.         {
  95.             long long temp = num[i];
  96.  
  97.             for(int j=0;j<k;j++)
  98.             {
  99.                 temp  =  search(root,temp,61);
  100.             }
  101.             mx = max(mx,temp);
  102.         }
  103.  
  104.         printf("Case #%d: %lld\n",l,mx);
  105.  
  106.  
  107.         del(root);
  108.     }
  109.  
  110.  
  111.  
  112.     return 0;
  113. }
  114.  
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
2
3 2
5 6 7
8 2
238 153 223 247 111 252 253 247
stdout
copy 
Case #1: 4
Case #2: 9
https://ideone.com/qJTOHy
language:
C++ (gcc 8.3)
created:
9 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!