-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathA_Bits.cpp
83 lines (63 loc) · 1.45 KB
/
A_Bits.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define TestCases int _test {1} ; cin >> _test ; while(_test--)
#define FAST ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
#define all(x) (x).begin() , (x).end()
#define nl "\n"
bool ispow2(int i) { return i && (i & -i) == i; }
int BIG = 1e18 ;
void sv(int l , int r )
{
auto ll = bitset<60>(l);
auto rr = bitset<60>(r);
auto maskk = (ll & rr);
int firstdiffer = -1 ;
for(int i = 59 ; i >= 0 ;i--)
{
if(ll[i]==rr[i] and ll[i]==maskk[i]) continue;
else
{
firstdiffer = i ;
break ;
}
}
bitset<60> mask2 = 0 ;
for(int i = firstdiffer - 1 ; i >= 0 ; i--)
{
mask2[i] = 1 ;
}
auto ans = (mask2 | maskk) ;
for(int i = max(l,r-10) ; i <= r ; i++)
{
if(__popcount(r)>ans.count())
{
ans = bitset<60>(i) ;
}
}
cout << ans.to_ullong() << nl ;
}
void solve()
{
int l , r ; cin >> l >> r ;
if(ispow2(r+1))
{
cout << r << nl ;
return ;
}
int leftmostbit = max(__bit_width(l) , __bit_width(r)) ;
int w1 = __bit_width(l) ;
int w2 = __bit_width(r) ;
if(w1!=w2)
{
int ans = ((1LL<<leftmostbit-1)-1) ;
cout << ans << nl;
return ;
}
else
{
sv(l,r) ;
return ;
}
}
signed main(){ FAST TestCases solve() ; }