fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int
  4. #define pii pair<int, int>
  5. #define REP(i, a, b) for (int i = a; i <= b; i++)
  6. #define RREP(i, a, b) for (int i = a; i >= b; i--)
  7. #define endl "\n"
  8. #define all(x) (x).begin(), (x).end()
  9. #define pi 3.141592653589793238
  10.  
  11. #define maxN 200001
  12. #define INF 1000000000
  13. #define mod 1000000007
  14. #define printd(x) cout << fixed << setprecision(10) << x
  15. // int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
  16. // int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
  17. // int dx[] = {-1, 0, 1, 0, 1, -1, 1, -1};
  18. // int dy[] = {0, -1, 0, 1, -1, -1, 1, 1};
  19.  
  20. const int sz = 2;
  21.  
  22. class TrieBit
  23. {
  24.     struct Node
  25.     {
  26.         Node *arr[sz];
  27.         int cnt;
  28.  
  29.         Node()
  30.         {
  31.             REP(i, 0, sz - 1)
  32.             arr[i] = NULL;
  33.             cnt = 0;
  34.         }
  35.     };
  36.  
  37.     Node *root;
  38.  
  39. public:
  40.     TrieBit()
  41.     {
  42.         root = new Node();
  43.     }
  44.  
  45.     void insert(ll s)
  46.     {
  47.         Node *temp = root;
  48.  
  49.         RREP(i, 63, 0)
  50.         {
  51.             if (s & (1LL << i))
  52.             {
  53.                 if (temp->arr[1] == NULL)
  54.                     temp->arr[1] = new Node();
  55.                 temp = temp->arr[1];
  56.             }
  57.             else
  58.             {
  59.                 if (temp->arr[0] == NULL)
  60.                     temp->arr[0] = new Node();
  61.                 temp = temp->arr[0];
  62.             }
  63.  
  64.             temp->cnt++;
  65.         }
  66.     }
  67.  
  68.     bool search(ll s)
  69.     {
  70.         Node *temp = root;
  71.  
  72.         RREP(i, 63, 0)
  73.         {
  74.             if (s & (1LL << i))
  75.             {
  76.                 if (temp->arr[1] == NULL || temp->arr[1]->cnt == 0)
  77.                     return false;
  78.                 temp = temp->arr[1];
  79.             }
  80.             else
  81.             {
  82.                 if (temp->arr[0] == NULL || temp->arr[0]->cnt == 0)
  83.                     return false;
  84.                 temp = temp->arr[0];
  85.             }
  86.         }
  87.  
  88.         return true;
  89.     }
  90.  
  91.     void del(ll s)
  92.     {
  93.         if (search(s) == false)
  94.             return;
  95.  
  96.         Node *temp = root;
  97.  
  98.         RREP(i, 63, 0)
  99.         {
  100.             if (s & (1LL << i))
  101.             {
  102.                 temp = temp->arr[1];
  103.             }
  104.             else
  105.             {
  106.                 temp = temp->arr[0];
  107.             }
  108.  
  109.             temp->cnt--;
  110.         }
  111.     }
  112.  
  113.     ll calc(ll s)
  114.     {
  115.         Node *temp = root;
  116.         ll ans = 0;
  117.  
  118.         RREP(i, 63, 0)
  119.         {
  120.             if (s & (1LL << i))
  121.             {
  122.                 if (temp->arr[0] && temp->arr[0]->cnt)
  123.                 {
  124.                     ans |= (1LL << i);
  125.                     temp = temp->arr[0];
  126.                 }
  127.                 else
  128.                 {
  129.                     temp = temp->arr[1];
  130.                 }
  131.             }
  132.             else
  133.             {
  134.                 if (temp->arr[1] && temp->arr[1]->cnt)
  135.                 {
  136.                     ans |= (1LL << i);
  137.                     temp = temp->arr[1];
  138.                 }
  139.                 else
  140.                 {
  141.                     temp = temp->arr[0];
  142.                 }
  143.             }
  144.         }
  145.  
  146.         return ans;
  147.     }
  148. };
  149.  
  150. int n;
  151. ll x;
  152. ll arr[maxN];
  153.  
  154. void solve()
  155. {
  156.     cin >> n >> x;
  157.  
  158.     REP(i, 1, n)
  159.     cin >> arr[i];
  160.  
  161.     TrieBit trie;
  162.  
  163.     ll ans = (x ^ arr[1]);
  164.     ll xo = arr[1];
  165.     trie.insert(arr[1]);
  166.  
  167.     REP(i, 2, n)
  168.     {
  169.         xo = (arr[i] ^ xo);
  170.         ans = max(ans, (xo ^ x));
  171.         trie.insert(xo);
  172.         ans = max(ans, trie.calc(x ^ xo));
  173.     }
  174.  
  175.     cout << (ans ^ x) << endl;
  176. }
  177.  
  178. int main(int argc, char const *argv[])
  179. {
  180.     ios_base::sync_with_stdio(false);
  181.     cin.tie(NULL);
  182.     cout.tie(NULL);
  183.  
  184.     // freopen("input.txt","r",stdin);
  185.     // freopen("output.txt","w",stdout);
  186.  
  187.     int t = 1;
  188.  
  189.     cin >> t;
  190.  
  191.     REP(tc, 1, t)
  192.     {
  193.         // cout<<"Case "<<tc<<":"<<endl;
  194.         solve();
  195.     }
  196.  
  197.     return 0;
  198. }
Success #stdin #stdout 0.01s 5536KB
comments (?)
stdin
copy 
3
3 7
1 2 3
15 15
26 7 8 21 3 5 6 5 9 4 2 6 5 2 2
10 16
1 2 3 4 5 6 7 8 9 10
stdout
copy 
0
16
15
https://ideone.com/Tl7mb7
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

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!