fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int N = 2e5 + 5; 
  12. const int MX = 6e6 + 5; 
  13.  
  14. template<typename T>
  15. void maximize(T& a, const T& b) {
  16. 	if (a < b) a = b;  
  17. }
  18.  
  19. struct Node {
  20. 	int nxt[2]; 
  21.  
  22. 	Node() {
  23. 		memset(nxt, -1, sizeof nxt); 
  24. 	}
  25. }; 
  26.  
  27. // Xem mỗi số như một xâu 30 bit, theo thứ tự từ bit 29 (lớn nhất) về bit 0 (nhỏ nhất) 
  28. int sz; 
  29. Node trie[MX]; 
  30.  
  31. void addNumber(int x) {
  32. 	int v = 0; 
  33. 	for (int i = 29; i >= 0; i--) {
  34. 		int bit = (x >> i) & 1; 
  35. 		if (trie[v].nxt[bit] == -1) {
  36. 			trie[v].nxt[bit] = ++sz; 
  37. 		}
  38. 		v = trie[v].nxt[bit]; 
  39. 	}
  40. }
  41.  
  42. // Tìm giá trị y ^ x lớn nhất trong các số y có trong cây trie hiện tại
  43. int getMaxXor(int x) {
  44. 	// Tại mỗi bước, ưu tiên đi vào nhánh cho ra xor bằng 1
  45. 	int v = 0, ans = 0; 
  46. 	for (int i = 29; i >= 0; i--) {
  47. 		int bit = (x >> i) & 1; 
  48. 		int nxt_v0 = trie[v].nxt[bit], nxt_v1 = trie[v].nxt[bit ^ 1]; 
  49. 		if (nxt_v1 != -1) {
  50. 			ans |= (1 << i); 
  51. 			v = nxt_v1;
  52. 		}
  53. 		else {
  54. 			v = nxt_v0; 
  55. 		}
  56. 	}
  57. 	return ans; 
  58. }
  59.  
  60. int n; 
  61. int a[N]; 
  62. int pref_xor[N]; 
  63.  
  64. int main() {
  65. 	ios::sync_with_stdio(false); 
  66. 	cin.tie(nullptr); 	
  67. 	cin >> n; 
  68. 	for (int i = 1; i <= n; i++) {
  69. 		cin >> a[i];  
  70. 		pref_xor[i] = pref_xor[i - 1] ^ a[i];  
  71. 	} 
  72.  
  73. 	int ans = 0;  
  74. 	for (int i = 0; i <= n; i++) {
  75. 		if (i > 0) maximize(ans, getMaxXor(pref_xor[i])); 
  76. 		addNumber(pref_xor[i]); 
  77. 	}
  78.  
  79. 	cout << ans << '\n'; 
  80. }
Success #stdin #stdout 0.01s 50348KB
comments (?)
stdin
copy 
4
5 1 5 9
stdout
copy 
13
https://ideone.com/Nm6Lc5
language:
C++14 (gcc 8.3)
created:
1 year 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!