fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using u128 = __uint128_t;
  4. using ull = unsigned long long;
  5. using i128 = __int128_t;
  6.  
  7. static inline int bitlen(unsigned long long x){
  8.     return x ? 64 - __builtin_clzll(x) : 0;
  9. }
  10.  
  11. static inline int popcnt(unsigned long long x){
  12.     return __builtin_popcountll(x);
  13. }
  14.  
  15. // x 이하에서 popcount를 최대화하는 수(같은 비트 길이 내에서)
  16. // 방법: MSB에서 내려오며, 처음 0을 만나는 순간 그 아래를 전부 1로 채움.
  17. static inline unsigned long long best_leq(unsigned long long x){
  18.     int L = bitlen(x);
  19.     if (x == ((L ? (1ULL<<L) : 0ULL) - 1)) return x; // 이미 all-ones
  20.     unsigned long long y = 0;
  21.     bool hitZero = false;
  22.     for (int i = L-1; i >= 0; --i){
  23.         ull bit = (x>>i)&1ULL;
  24.         if (hitZero){
  25.             y |= (1ULL<<i);               // 아래 비트 전부 1
  26.         }else{
  27.             if (bit) y |= (1ULL<<i);      // prefix 유지
  28.             else     hitZero = true;      // 첫 0: 여긴 0, 아래는 1로 채움
  29.         }
  30.     }
  31.     return y;
  32. }
  33.  
  34. static inline int g_of_x(ull x){
  35.     return bitlen(x) - popcnt(x);
  36. }
  37.  
  38. int main(){
  39.     ios::sync_with_stdio(false);
  40.     cin.tie(nullptr);
  41.     int T; 
  42.     if(!(cin>>T)) return 0;
  43.     while(T--){
  44.         unsigned long long a,b; cin>>a>>b;
  45.         // 1) [a,b]에 2의 거듭제곱이 있으면 답 0
  46.         ull p = 1ULL << (bitlen(b)-1);    // b 이하 최댓 2의 거듭제곱
  47.         if (p >= a){ 
  48.             cout << 0 << '\n';
  49.             continue;
  50.         }
  51.         ull A = a-1, B = b-1;
  52.         int ans = INT_MAX;
  53.         // 후보 집합(중복 방지용)
  54.         vector<ull> cand;
  55.         auto push = [&](ull x){
  56.             if (x < A || x > B) return;
  57.             cand.push_back(x);
  58.         };
  59.  
  60.         // 2) B 기반 후보
  61.         push(best_leq(B));
  62.         // 경계값도 넣어둠
  63.         push(A);
  64.         push(B);
  65.  
  66.         // 3) A의 각 0비트를 올리고 아래를 1로 채운 후보들
  67.         int LA = bitlen(A);
  68.         for (int i = 0; i < LA; ++i){
  69.             if (((A>>i)&1ULL)==0ULL){
  70.                 ull z = A | (1ULL<<i);
  71.                 z |= ((1ULL<<i)-1);   // 아래 전부 1
  72.                 push(z);
  73.             }
  74.         }
  75.         // 4) 비트 길이 구간별 상단에서의 후보들
  76.         int LB = bitlen(B);
  77.         for (int L = bitlen(A); L <= LB; ++L){
  78.             ull low  = max<ull>(A, (L? (1ULL<<(L-1)) : 0ULL));
  79.             ull high = min<ull>(B, (L? ((1ULL<<L)-1) : 0ULL));
  80.             if (low <= high){
  81.                 push(best_leq(high));
  82.             }
  83.         }
  84.  
  85.         // 평가
  86.         for (ull x: cand){
  87.             ans = min(ans, g_of_x(x));
  88.         }
  89.         cout << ans << '\n';
  90.     }
  91.     return 0;
  92. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
4
3 10
5 6
3 3
1766147374 1766147446
stdout
copy 
0
1
1
15
https://ideone.com/0Mw4px
language:
C++ (gcc 8.3)
created:
1 day 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!