oj.uz

답안 #41564

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
41564 2018-02-19T04:31:43 Z pica4500 비교 (balkan11_cmp) C++
100 / 100
 2482 ms 92956 KB 
#include "cmp.h"

//3bit compression with Tree
int getIdx(int n, int kth) {
	n >>= (kth * 3 - 3);
	n %= 8;
	return (n + 1);
}

int getKthLayer(int n, int kth) {
	int cur = 0;
	for (int i = 4; i >= kth; i--) {
		cur *= 8;
		cur += getIdx(n, i);
	}
	return cur;
}

void remember(int n) {
	int cur = 0;
	for (int i = 4; i > 0; i--) {
		cur *= 8;
		cur += getIdx(n, i);
		bit_set(cur);
	}
}

int compare(int b) {
	int l = 4, r = 1, mid = 2;
	while (l >= r) {
		mid = (l + r) / 2;
		if (bit_get(getKthLayer(b, mid))) l = mid - 1;
		else r = mid + 1;
	}
	if (l == 0) return 0;
	int idx = getKthLayer(b, l);
	int c = ((idx - 1) % 8) + 1;
	if (c < 5) {
		for (int i = c - 1; i > 0; i--)
			if (bit_get(idx - (c - i))) return 1;
		return -1;
	}
	else {
		for (int i = c + 1; i < 9; i++)
			if (bit_get(idx + (i - c))) return -1;
		return 1;
	}
	return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2482 ms 92956 KB Output is correct - maxAccess = 10, score = 100