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. template<typename T>
  12. void maximize(T& a, const T& b) {
  13. 	if (a < b) a = b;  
  14. }
  15.  
  16. vector<int> digit_l, digit_r;  
  17.  
  18. vector<int> getDigit(ll n) {
  19. 	vector<int> ans; 
  20. 	for (; n > 0; n >>= 1) ans.push_back(n & 1); 
  21. 	return ans; 
  22. }
  23.  
  24. // larger_a, smaller_a: điều kiện smaller, larger của số a
  25. // larger_b, smaller_b: điều kiện smaller, larger của số b
  26. // dp = Giá trị XOR lớn nhất của phần còn lại khi phần prefix 
  27. //      trước vị trí idx của a và b mang theo điều kiện smaller, larger tương ứng
  28. ll memo[60][2][2][2][2];
  29.  
  30. ll dp(int idx, bool larger_a, bool smaller_a, bool larger_b, bool smaller_b) {
  31. 	if (idx == -1) return 0;
  32.  
  33. 	ll& ans = memo[idx][larger_a][smaller_a][larger_b][smaller_b]; 
  34. 	if (ans != -1) return ans;   
  35.  
  36. 	ans = 0;  
  37. 	int min_digit_a = (larger_a) ? 0 : digit_l[idx]; 
  38. 	int max_digit_a = (smaller_a) ? 1 : digit_r[idx]; 
  39. 	int min_digit_b = (larger_b) ? 0 : digit_l[idx]; 
  40. 	int max_digit_b = (smaller_b) ? 1 : digit_r[idx]; 
  41.  
  42. 	for (int a_i = min_digit_a; a_i <= max_digit_a; a_i++) {
  43. 		for (int b_i = min_digit_b; b_i <= max_digit_b; b_i++) {
  44. 			ll val = (a_i ^ b_i) * (1ll << idx); 
  45. 			maximize(ans, val + dp(idx - 1, larger_a | (a_i > digit_l[idx]), smaller_a | (a_i < digit_r[idx]), 
  46. 											larger_b | (b_i > digit_l[idx]), smaller_b | (b_i < digit_r[idx]))); 
  47. 		}
  48. 	}
  49.  
  50. 	return ans; 
  51. }
  52.  
  53. ll solve(ll l, ll r) {
  54. 	digit_l = getDigit(l); 
  55. 	digit_r = getDigit(r); 
  56. 	while (digit_l.size() < digit_r.size()) digit_l.push_back(0); 
  57. 	memset(memo, -1, sizeof memo); 
  58. 	return dp(digit_r.size() - 1, 0, 0, 0, 0); 
  59. }
  60.  
  61. int main() {
  62. 	ios::sync_with_stdio(false); 
  63. 	cin.tie(nullptr); 	
  64. 	ll l, r; 
  65. 	cin >> l >> r; 
  66.  
  67. 	ll ans = solve(l, r); 
  68.  
  69. 	cout << ans << '\n';
  70. }
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
1 2
stdout
copy 
3
https://ideone.com/lVqBBU
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!