Unratedになってよかった…。
Aで4WAした上、B,Dも解いたと思ったらsystest通ってなかった。
http://codeforces.com/contest/484/problem/A
問題
N個の独立したクエリが与えられるので、それぞれに答えよ。
各クエリは2整数L,Rからなるので、L≦x≦Rの範囲の整数xのうち、2進数表記で1が最多のものを答えよ。
1が最多な整数が複数ある場合、最小値を答えよ。
解法
L==RならL==R==x一択。
L<Rなら、下記のように上の桁から見てLでは0、Rでは1になるケースがある。
L = XXXX0YYYY(2) R = XXXX1ZZZZ(2)
この時:
- LとRで異なる桁が一番下の桁なら、x=Rが解。
- ZZZZ=1111なら、x=Rが解。
- 上記2つのいずれでもないなら、x=XXXX01111が解。
ll dodo(ll x,ll y) { for(int i=62;i>=0;i--) if((x&(1LL<<i))!=(y&(1LL<<i))) { if((y&((1LL<<i)-1))==((1LL<<i)-1)) return y; return x|((1LL<<i)-1); } return y; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) { ll L,R; cin>>L>>R; cout << dodo(L,R) << endl; } }
まとめ
地味にちょこちょこコーナーケースがあって厄介。