UVA – 10718 – Bit Mask   1 comment


#include <stdio.h>
typedef long long int ll;
ll solve(ll L, ll U, ll N) {
	ll res = 0;
	int gt = 0;
	int i;
	for (i = 31; i >= 0; i--) {
		if (gt) {
			if ((U & (1LL << i)) && !(N & (1LL << i)))
				res |= 1LL << i;
			else if ((U & (1LL << i)))
				U |= (1LL << i) - 1;
		} else {
			if ((U & (1LL << i)) && (L & (1L << i)))
				res |= 1LL << i;
			else if ((U & (1LL << i)) && !(N & (1LL << i))) {
				res |= 1LL << i;
				gt = 1;
			} else if ((U & (1LL << i)))
				U |= (1LL << i) - 1;
		}
	}
	return res;
}
int main() {
	ll N, L, U;
	while (scanf("%lld %lld %lld", &N, &L, &U) == 3)
		printf("%lld\n", solve(L, U, N));
	return 0;
}

Advertisements

Posted July 5, 2012 by epicrado in Greedy

One response to “UVA – 10718 – Bit Mask

Subscribe to comments with RSS.

  1. The part inside for loop can simply be replaced with this:
    if (((N & (1LL << i)) == 0 && (res + (1LL << i)) <= U)|| (res + (1LL << i) – 1) < L) {
    res |= (1L << i);
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: