Codeforces #276 Div1 A. Bits

Unratedになってよかった…。
Aで4WAした上、B,Dも解いたと思ったらsystest通ってなかった。
http://codeforces.com/contest/484/problem/A

問題

N個の独立したクエリが与えられるので、それぞれに答えよ。

各クエリは２整数L,Rからなるので、L≦x≦Rの範囲の整数xのうち、２進数表記で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が解。
• 上記２つのいずれでもないなら、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;
	}
	
}

まとめ

地味にちょこちょこコーナーケースがあって厄介。