BOJ 13505 두 수 XOR

Source.cpp

#include <stdio.h>
//#include <crtdbg.h>

int power_2[30];

struct Trie
{
	Trie *child[2];

	Trie()
	{
		child[0] = NULL;
		child[1] = NULL;
	}

	~Trie()
	{
		if (child[0] != NULL) delete child[0];
		if (child[1] != NULL) delete child[1];
	}

	void insert(int value, int exponent)
	{
		if (exponent == -1) return;
		if (value >= power_2[exponent])
		{
			if (child[1] == NULL) child[1] = new Trie;
			child[1]->insert(value - power_2[exponent], exponent - 1);
		}
		else
		{
			if (child[0] == NULL) child[0] = new Trie;
			child[0]->insert(value, exponent - 1);
		}
	}

	int find(int value, int exponent)
	{
		if (exponent == -1) return 0;
		if (value >= power_2[exponent])
		{
			if (child[0] != NULL) return child[0]->find(value - power_2[exponent], exponent - 1);
			else return power_2[exponent]+child[1]->find(value - power_2[exponent], exponent - 1);
		}
		else
		{
			if (child[1] != NULL) return power_2[exponent] + child[1]->find(value, exponent - 1);
			else return child[0]->find(value, exponent - 1);
		}
	}
};

int main()
{
	//freopen("input.txt", "r", stdin);
	//_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
	Trie root;
	int multiply = 1, N, answer = 0, input[100000];
	for (int i = 0; i < 30; i++)
	{
		power_2[i] = multiply;
		multiply *= 2;
	}
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
	{
		scanf("%d", &input[i]);
		root.insert(input[i], 29);
	}
	for (int i = 0; i < N; i++)
	{
		int temp = root.find(input[i], 29);
		if ((temp^input[i]) > answer) answer = (temp^input[i]);
	}
	printf("%d\n", answer);
	return 0;
}