Submission #41564

#	Time	Username	Problem	Language	Result	Execution time	Memory
41564		pica4500	cmp (balkan11_cmp)	C++98	100 / 100	2482 ms	92956 KiB

cmp

#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 / 100