Submission #4690

#	Time	Username	Problem	Language	Result	Execution time	Memory
4690		tncks0121	cmp (balkan11_cmp)	C++98	46 / 100	2109 ms	104984 KiB

cmp

#include "cmp.h"

void remember(int n) {
	n += 4096;
	while(n > 1) {
		bit_set(n);
		n >>= 1;
	}
}

int compare(int b) {
	b += 4096;

	int low = 0, high = 12;
	int btop = -1;
	while(low <= high) {
		int mid = (low+high) >> 1;
		if((b>>mid) != 1 && !bit_get(b >> mid)) {
			btop = b >> mid;
			low = mid + 1;
		}else {
			high = mid - 1;
		}
	}

	if(btop == -1) return 0;

	/*

	  lca
	 /   \
	a     !

	   lca
	  /   \
	 /\   /\
	  b     a	
	*/

	int atop = (btop / 2) * 2;
	if(btop / 2 * 2 == btop) ++atop;

	return atop < btop ? 1 : -1;
}

• Subtask 1: 46 / 100