Advertisement
Galebickosikasa

Untitled

Aug 19th, 2020
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.97 KB | None | 0 0
  1. #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
  2. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx")
  3. // #pragma comment(linker, "/stack:200000000"]
  4.  
  5. #include <iostream>
  6. #include <vector>
  7. #include <cmath>
  8. #include <algorithm>
  9. #include <unordered_set>
  10. #include <unordered_map>
  11. #include <set>
  12. #include <map>
  13. #include <queue>
  14. #include <deque>
  15. #include <bitset>
  16. #include <stack>
  17. #include <random>
  18. #include <fstream>
  19. #include <sstream>
  20. #include <chrono>
  21.  
  22. #define fi first
  23. #define se second
  24. #define pb push_back
  25. #define ll long long
  26. #define ld long double
  27. #define hm unordered_map
  28. #define pii pair<int, int>
  29. #define sz(a) (int)a.size()
  30. #define all(a) a.begin(), a.end()
  31. #define cinv(v) for (auto& x: v) cin >> x
  32. #define fr(i, n) for (int i = 0; i < n; ++i)
  33. #define fl(i, l, n) for (int i = l; i < n; ++i)
  34.  
  35. #define int ll
  36.  
  37. using namespace std;
  38.  
  39. #ifdef __LOCAL
  40. #define dbg(x) cerr << #x << " : " << x << '\n'
  41. const int maxn = 20;
  42. #else
  43. #define dbg(x)
  44. const int maxn = 2e5 + 20;
  45. #endif
  46.  
  47. //tg: @galebickosikasa
  48.  
  49. ostream& operator << (ostream& out, vector<int>& v) {
  50. for (auto& x: v) out << x << ' ';
  51. return out;
  52. }
  53.  
  54. ostream& operator << (ostream& out, pii& v) {
  55. out << v.fi << ", " << v.se;
  56. return out;
  57. }
  58.  
  59. istream& operator >> (istream& in, pii& a) {
  60. in >> a.fi >> a.se;
  61. return in;
  62. }
  63.  
  64. const ll inf = (ll) 2e9;
  65. const ld pi = asin (1) * 2;
  66. const ld eps = 1e-8;
  67. const ll mod = (ll)1e9 + 7;
  68. const ll ns = 97;
  69.  
  70. mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
  71.  
  72. int ans = 0, s, t, deep = 31, flag = 0;
  73. int f[35], g[35];
  74.  
  75. int left (int v, int d) {
  76. return v - g[d + 2] - 1;
  77. }
  78.  
  79. int right (int v, int d) {
  80. return v + g[d + 2] + 1;
  81. }
  82.  
  83. void dfs (int v = (1<<30), int d = 1, int state = 0) {
  84. if (state == 0) {
  85. if (s <= v && v <= t) {
  86. if (v != s) {
  87. ans += max (0ll, deep - d - 1);
  88. dfs (left (v, d), d + 1, 1);
  89. }
  90. if (v != t) {
  91. ans += max (0ll, deep - d - 1);
  92. dfs (right (v, d), d + 1, 2);
  93. }
  94. } else {
  95. if (v < s) dfs (right (v, d), d + 1, 0);
  96. else dfs (left (v, d), d + 1, 0);
  97. }
  98. } else if (state == 1) {
  99. if (v == s) {
  100. ans += f[d + 1] + max (0ll, deep - d - 1);
  101. dbg (ans);
  102. return;
  103. }
  104. if (v > s) {
  105. ans += f[d + 1] + (max (0ll, deep - d - 1)) * 2;
  106. dfs (left (v, d), d + 1, 1);
  107. } else {
  108. dfs (right (v, d), d + 1, 1);
  109. }
  110. } else {
  111. if (v == t) {
  112. ans += f[d + 1] + max (0ll, deep - d - 1);
  113. return;
  114. }
  115. if (v > t) {
  116. dfs (left (v, d), d + 1, 2);
  117. } else {
  118. ans += f[d + 1] + (max (0ll, deep - d - 1)) * 2;
  119. dfs (right (v, d), d + 1, 2);
  120. }
  121. }
  122. }
  123.  
  124. signed main () {
  125. ios_base::sync_with_stdio(false);
  126. cin.tie(nullptr);
  127. cout.tie(nullptr);
  128. f[31] = f[30] = 0;
  129. int c = 1;
  130. for (int i = 29; i >= 0; --i) {
  131. f[i] = (f[i + 1] + c) * 2;
  132. ++c;
  133. }
  134. fr (i, 32) g[i] = (1ll<<(32 - i)) - 1;
  135. cin >> s >> t;
  136. if (s > t) swap (s, t);
  137. dfs ();
  138. cout << ans << '\n';
  139.  
  140.  
  141.  
  142.  
  143.  
  144.  
  145. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement