fork download
copy 
  1. /*
  2. 	B - The Sparsest Number in Between
  3. */
  4.  
  5. #include <bits/stdc++.h>
  6. #include <ext/pb_ds/tree_policy.hpp>
  7. #include <ext/pb_ds/assoc_container.hpp> 
  8.  
  9. using namespace std;
  10. using namespace __gnu_pbds;
  11.  
  12. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update > pbds;
  13. // find_by_order, order_by_key
  14.  
  15. #define sp << " " << 
  16. #define ll unsigned long long
  17. #define ld long double
  18. #define pb push_back
  19. #define F first
  20. #define S second
  21. #define PI 3.1415926535897932384626
  22.  
  23. #define all(x) x.begin(), x.end()
  24. #define rall(x) x.rbegin(), x.rend()
  25. #define sortall(x) sort(all(x))
  26. #define sortrall(x) sort(rall(x))
  27.  
  28. #define printv(v) for(auto x : v) cout << x << " "; cout << "\n"
  29. #define printm(m) for(auto x : m) cout << x.F sp x.S << "\n"
  30.  
  31. #define make_unique(x) sortall(x); (x).resize(unique(all(x)) - (x).begin())
  32. #define numtobin(n) bitset<64>(n).to_string() 
  33. #define bintoint(bin_str) stoi(bin_str, nullptr, 2)
  34. #define bintoll(bin_str) stoll(bin_str, nullptr, 2)
  35.  
  36. struct custom_hash {
  37.     static uint64_t splitmix64(uint64_t x) {
  38.         x += 0x9e3779b97f4a7c15;
  39.         x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  40.         x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  41.         return x ^ (x >> 31);
  42.     }
  43.  
  44.     size_t operator()(uint64_t x) const {
  45.         static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
  46.         return splitmix64(x + FIXED_RANDOM);
  47.     }
  48. };
  49.  
  50. template<typename T1, typename T2>
  51. using safe_map = unordered_map<T1, T2, custom_hash>;
  52.  
  53. template<typename T>
  54. using safe_set = unordered_set<T, custom_hash>;
  55.  
  56. template<typename T>
  57. void debug(T x) { cerr << x << endl; }
  58.  
  59. template<typename T, typename... Args>
  60. void debug(T x, Args... args) { cerr << x << " "; debug(args...); }
  61.  
  62. void fastIO() {
  63.     ios_base::sync_with_stdio(false);
  64.     cin.tie(NULL); cout.tie(NULL);
  65. }
  66.  
  67. void fraction() {
  68.     cout.unsetf(ios::floatfield); 
  69.     cout.precision(10); 
  70.     cout.setf(ios::fixed,ios::floatfield);
  71. }
  72.  
  73. void yn(bool res, bool cap = true) {
  74.     vector<string> s = {"Yes", "YES", "No", "NO"};
  75.     cout << ((res) ? s[0 + cap] : s[2 + cap]) << "\n";
  76. }
  77.  
  78. void chmin(ll &x, ll y) { x = min(x, y); }
  79. void chmax(ll &x, ll y) { x = max(x, y); }
  80.  
  81. inline ll nxt() { ll x; cin >> x; return x;}
  82. inline ld nxtD() { ld x; cin >> x; return x;}
  83. inline string nxtStr() { string x; cin >> x; return x;}
  84.  
  85. const int mod = 1e9 + 7;
  86. const int INF = 1e9;
  87. const ll LINF = 1e18;
  88.  
  89. void proc(){
  90.  
  91. }
  92. // stress testing 
  93. int sol(int x, int y) {
  94.     int ans = x;
  95.     int cnt = __builtin_popcount(x);
  96.     while(y >= x) {
  97.         int r = __builtin_popcount(x);
  98.         if(cnt > r) {
  99.             cnt = r;
  100.             ans = x;
  101.         }
  102.         x++;
  103.     }
  104.  
  105.     return ans;
  106. }
  107.  
  108. void solve(int xl = 1, int xr = 1) {
  109.     ll a, b; cin >> a >> b;
  110.     // ll a = xl, b = xr;
  111.     ll ans = a;
  112.     bool p = false;
  113.  
  114.     auto countBit = [&](ll x) ->int {
  115.         int res = 0;
  116.         while(x){
  117.             if(x & 1) res++;
  118.             x >>= 1;
  119.         }
  120.         return res;
  121.     };
  122.  
  123.     for(int i = 0; i < 64; i++) {
  124.         ll p = (1ll << i);
  125.         if(a <= p && p <= b) {
  126.             cout << p << "\n";
  127.             return;
  128.         }
  129.     }
  130.  
  131.     int l = countBit(a);
  132.  
  133.     for(int i = 64; i >= 0; i--) {
  134.         if ((a >> i) & 1) p = true;
  135.         if(!((a >> i) & 1) && ((b >> i) & 1) && p) {
  136.             ll tmp = a;
  137.             int l = i;
  138.             while(i--) {
  139.                 if((tmp >> i) & 1)
  140.                     tmp ^= (1ll << i);
  141.             }
  142.  
  143.             for(int j = 0; j <= l; j++) {
  144.                 if((tmp | (1ll << j)) >= a) {
  145.                     tmp |= (1ll << j);
  146.                     a = tmp;
  147.                     break;
  148.                 }
  149.             }
  150.             break;
  151.         }
  152.     }    
  153.     int r = countBit(a);
  154.  
  155.     if(r == l) ans = min(a, ans);
  156.     else if(l > r) ans = a;
  157.  
  158.     cout << ans << "\n";
  159.     // ll chk = sol(xl, xr);
  160.     // yn(chk == ans);
  161.     // debug(xl, xr, ans, sol(xl, xr));
  162. }
  163.  
  164. int main() {
  165.     fastIO(); 
  166.     proc();
  167.  
  168.     int tc = 1;
  169.     // tc = nxt();
  170.     for (int t = 1; t <= tc; t++) {
  171.         // cout << "Case " << t << ": ";
  172.         solve();
  173.     }
  174.  
  175.     // for(int i = 1; i <= 50; i++) {
  176.     //     for(int j = i; j <= 50; j++) {
  177.     //         solve(i, j);
  178.     //     }
  179.     // }
  180. }
  181.  
  182.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
11 15
stdout
copy 
12
https://ideone.com/r4e75u
language:
C++14 (clang 8.0)
created:
7 hours 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!