fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int
  4. #define endl "\n"
  5.  
  6. struct binaryTrie
  7. {
  8. 	struct Node
  9. 	{
  10. 		Node *child[2];
  11. 		int freq[2];
  12. 		Node()
  13. 		{
  14. 			child[0] = child[1] = 0;
  15. 			freq[0] = freq[1] = 0;
  16. 		}
  17. 	};
  18. 	Node *root = new Node();
  19.  
  20. 	binaryTrie()
  21. 	{
  22. 	}
  23. 	void insert(ll n)
  24. 	{
  25. 		Node *cur = root;
  26. 		for (int i = 40; i >= 0; i--) // change 30 based on number of bits in maximum number
  27. 		{
  28. 			int idx = ((n >> i) & 1); // same as (n & (1 << i)), but this avoids any overflow
  29. 			if (cur->child[idx] == 0)
  30. 				cur->child[idx] = new Node();
  31. 			cur->freq[idx]++;
  32. 			cur = cur->child[idx];
  33. 		}
  34. 	}
  35. 	void erase(ll n, int i, Node *cur)
  36. 	{
  37. 		if (i == -1)
  38. 			return;
  39. 		int idx = ((n >> i) & 1);
  40. 		erase(n, i - 1, cur->child[idx]);
  41. 		cur->freq[idx]--;
  42. 		if (cur->freq[idx] == 0)
  43. 		{
  44. 			delete cur->child[idx];
  45. 			cur->child[idx] = NULL;
  46. 		}
  47. 	}
  48. 	ll maxXor(ll n)
  49. 	{
  50. 		Node *cur = root;
  51. 		ll ret = 0;
  52. 		for (int i = 40; i >= 0; i--) // change 30 based on number of bits in maximum number
  53. 		{
  54. 			ll idx = ((n >> i) & 1); // same as (n & (1 << i)), but this avoids any overflow
  55. 			if (cur->child[idx ^ 1] != 0)
  56. 				cur = cur->child[idx ^ 1], ret |= (1 << i);
  57. 			else
  58. 				cur = cur->child[idx];
  59. 		}
  60. 		return ret;
  61. 	}
  62. };
  63.  
  64. int main()
  65. {
  66. 	ios_base::sync_with_stdio(false);
  67. 	cin.tie(nullptr);
  68. 	cout.tie(nullptr);
  69. #ifndef ONLINE_JUDGE
  70. 	freopen("input.txt", "r", stdin);
  71. 	freopen("Output.txt", "w", stdout);
  72. #endif //! ONLINE_JUDGE
  73. 	int t = 1;
  74. 	ll N, K;
  75. 	// cin >> t;
  76. 	while (t--)
  77. 	{
  78. 		cin >> N;
  79. 		vector<ll> a(N);
  80. 		binaryTrie binTrie;
  81. 		ll pref{};
  82. 		for (int i{}; i < N; i++)
  83. 			cin >> a[i], pref ^= a[i];
  84.  
  85. 		ll suff{};
  86. 		for (int i = N - 1; i >= 0; i--)
  87. 		{
  88. 			suff ^= a[i];
  89. 			binTrie.insert(suff);
  90. 		}
  91.  
  92. 		ll mx = 0, x{};
  93. 		for (int i = 0; i < N; i++)
  94. 		{
  95. 			mx = max(binTrie.maxXor(x) ^ x, mx);
  96. 			x ^= a[i];
  97. 		}
  98. 		mx = max(binTrie.maxXor(x) ^ x, mx);
  99.  
  100. 		cout << mx << endl;
  101. 	}
  102. 	return 0;
  103. }
Success #stdin #stdout #stderr 0.26s 40680KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Error: unexpected symbol in "using namespace"
Execution halted
https://ideone.com/YMCMqp
language:
R (R 3.5.2)
created:
6 days 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!