oj.uz

답안 #4694

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
4694 2013-12-17T13:04:54 Z tncks0121 비교 (balkan11_cmp) C++
91 / 100
 2033 ms 102252 KB 
#include "cmp.h"

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

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

	int low = 0, high = 6;
	int btop = -1;

	while(low <= high) {
		int mid = (low+high) >> 1;

		if(mid != 6 && !bit_get(b >> (mid*2))) {
			btop = b >> (mid*2);
			low = mid + 1;
		}else {
			high = mid - 1;
		}
	}

	if(btop == -1) return 0;
	

	switch(btop % 4) {
	case 0:
		return -1;
	case 3:
		return 1;
	case 1:
		return bit_get(btop/4*4+2) || bit_get(btop/4*4+3) ? -1 : 1;
	case 2:
		return bit_get(btop/4*4+0) || bit_get(btop/4*4+1) ? 1 : -1;
	}

	return 0;
}


/*

   lca
__________
|  |  |  |
A  B  C  D

A에 있다: b < a
D에 있다: b > a
B에 있다: C에 있거나 D에 있다
C에 있다: A에 있거나 B에 있다


*/

Subtask #1
91.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 2033 ms 102252 KB Output is partially correct - maxAccess = 11, score = 91