Submission #5609

#	Time	Username	Problem	Language	Result	Execution time	Memory
5609		kriii	cmp (balkan11_cmp)	C++98	100 / 100	1998 ms	82936 KiB

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