Advertisement
Guest User

Untitled

a guest
Dec 11th, 2019
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.75 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
  6. #define sz(a) int((a).size())
  7.  
  8. #define x first
  9. #define y second
  10.  
  11. typedef long long li;
  12.  
  13. li n, k;
  14.  
  15. inline bool read() {
  16.     if(!(cin >> n >> k))
  17.         return false;
  18.     return true;
  19. }
  20.  
  21. int getLen(li val) {
  22.     int ans = 0;
  23.     while(val > 0) {
  24.         ans++;
  25.         val >>= 1;
  26.     }
  27.     return ans;
  28. }
  29.  
  30. li calcSize(li val, li mx) {
  31.     if(val > mx)
  32.         return 0;
  33.  
  34.     int diffLen = getLen(mx) - getLen(val);
  35.    
  36.     li ans = 0;
  37.     fore(k, 0, diffLen)
  38.         ans += 1ll << k;
  39.     if(val > (mx >> diffLen))
  40.         return ans;
  41.     if(val < (mx >> diffLen))
  42.         ans += 1ll << diffLen;
  43.     else
  44.         ans += mx - (val << diffLen) + 1;
  45.     return ans;
  46. }
  47.  
  48. li calcSubTree(li val, li mx) {
  49.     if(val & 1ll)
  50.         return calcSize(val, mx);
  51.     return calcSize(val, mx) + calcSize(val + 1, mx);
  52. }
  53.  
  54. inline void solve() {
  55.     li lvl = 1;
  56.     for(li curL = 1ll; curL <= n; curL <<= 1) {
  57.         if(calcSubTree(curL, n) >= k)
  58.             lvl = curL;
  59.     }
  60.    
  61.     li ans = 0;
  62.    
  63.     li lf = lvl / 2, rg = lvl;
  64.     while(rg - lf > 1) {
  65.         li mid = (lf + rg) >> 1;
  66.         if(calcSubTree(2 * mid, n) >= k)
  67.             lf = mid;
  68.         else
  69.             rg = mid;
  70.     }
  71.     ans = max(ans, 2 * lf);
  72.    
  73.     lf = lvl / 2, rg = lvl;
  74.     while(rg - lf > 1) {
  75.         li mid = (lf + rg) >> 1;
  76.         if(calcSubTree(2 * mid + 1, n) >= k)
  77.             lf = mid;
  78.         else
  79.             rg = mid;
  80.     }
  81.     if(calcSubTree(2 * lf + 1, n) >= k)
  82.         ans = max(ans, 2 * lf + 1);
  83.    
  84.     cout << ans << endl;
  85. }
  86.  
  87. int main() {
  88. #ifdef _DEBUG
  89.     freopen("input.txt", "r", stdin);
  90.     int tt = clock();
  91. #endif
  92.     ios_base::sync_with_stdio(false);
  93.     cin.tie(0), cout.tie(0);
  94.     cout << fixed << setprecision(15);
  95.    
  96.     if(read()) {
  97.         solve();
  98.        
  99. #ifdef _DEBUG
  100.         cerr << "TIME = " << clock() - tt << endl;
  101.         tt = clock();
  102. #endif
  103.     }
  104.     return 0;
  105. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement