Submission #41564

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
41564	2018-02-19T04:31:43 Z	pica4500	cmp (balkan11_cmp)	C++	100 / 100	2482 ms	92956 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2482 ms	92956 KB	Output is correct - maxAccess = 10, score = 100