답안 #5609

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
5609	2014-05-07T02:31:18 Z	kriii	비교 (balkan11_cmp)	C++	100 / 100	1998 ms	82936 KB

cmp

#include "cmp.h"
// 팔진트리를 두개만들어서 하나는 앞의 6비트, 하나는 뒤의 6비트를 보게 하였음

inline int par(int v){
	return (v - 1) / 8;
}

const int Y = 100;
const int Z = 1 + (1 << 3);

void remember(int a)
{
	int A[2],i;
	A[0] = a / 64;
	A[1] = a % 64;

	for (i=0;i<2;i++){
		a = A[i] + Z;

		while (a){
			bit_set(a+Y*i);
			a = par(a);
		}
	}
}

int compare(int b)
{
	int B[2],i;
	B[0] = b / 64;
	B[1] = b % 64;

	for (i=0;i<2;i++){
		b = B[i] + Z;

		if (bit_get(b+Y*i)) continue;

		while (par(b)){
			if (bit_get(par(b)+Y*i)) break;
			b = par(b);
		}
		int pos = (b - 1) % 8;

		if (pos < 4){
			while (--pos >= 0){
				b--;
				if (bit_get(b+Y*i)) return 1;
			}
			return -1;
		}

		while (++pos < 8){
			b++;
			if (bit_get(b+Y*i)) return -1;
		}
		return 1;
	}
	return 0;
}

Subtask #1

100.0 / 100.0

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