#163460 (C++11) No.130 XOR Minimax

• 問題: No.130 XOR Minimax
• ユーザー: kurenai3110
• 提出日時: 2017-04-04 04:40:47
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 484 ms / 5,000 ms
• コード長: 1,582 bytes
• コンパイル時間: 1,223 ms
• コンパイル使用メモリ: 69,084 KB
• 実行使用メモリ: 61,708 KB
• 最終ジャッジ日時: 2023-10-10 00:17:48
• 合計ジャッジ時間: 7,822 ms
• ジャッジサーバーID （参考情報）: judge12 / judge15

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	233 ms; 28,232 KB
testcase_01	AC	1 ms; 4,376 KB
testcase_02	AC	2 ms; 4,376 KB
testcase_03	AC	1 ms; 4,372 KB
testcase_04	AC	319 ms; 13,996 KB
testcase_05	AC	357 ms; 14,052 KB
testcase_06	AC	357 ms; 20,224 KB
testcase_07	AC	380 ms; 20,240 KB
testcase_08	AC	484 ms; 61,708 KB
testcase_09	AC	57 ms; 6,560 KB
testcase_10	AC	89 ms; 7,928 KB
testcase_11	AC	312 ms; 16,844 KB
testcase_12	AC	28 ms; 5,056 KB
testcase_13	AC	251 ms; 14,496 KB
testcase_14	AC	463 ms; 50,576 KB
testcase_15	AC	5 ms; 4,376 KB
testcase_16	AC	324 ms; 36,920 KB
testcase_17	AC	337 ms; 38,272 KB
testcase_18	AC	368 ms; 40,952 KB
testcase_19	AC	435 ms; 47,708 KB
testcase_20	AC	208 ms; 25,632 KB
testcase_21	AC	465 ms; 50,052 KB
testcase_22	AC	96 ms; 13,932 KB
testcase_23	AC	29 ms; 6,744 KB

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

struct Trie {
	Trie *next[2];

	Trie() {
		fill(next, next + 2, (Trie *)0);
	}

	void insert(const char *s) {
		if (*s == '\0') return;
		if (this->next[*s-'0'] == NULL)
			this->next[*s-'0'] = new Trie();
		this->next[*s-'0']->insert(s + 1);
	}

	bool find(const char *s) {
		if (*s == '\0') return true;
		if (this->next[*s-'0'] == NULL)
			return false;
		return this->next[*s-'0']->find(s + 1);
	}
};

string binary(int a, int l = 32) {
	string s = "";
	for (int i = 0; i < l; i++) {
		s += to_string(a & 1);
		a >>= 1;
	}
	reverse(s.begin(), s.end());
	return s;
}
int binary_to_int(string bi) {
	int a = 0;
	for (int i = 0; i < bi.size(); i++) {
		a += (bi[bi.size() - 1 - i] - '0') << i;
	}
	return a;
}

string solve(Trie* trie) {
	bool exist0 = trie->find("0"), exist1 = trie->find("1");
	string bi = "";

	if (exist0 && !exist1)bi = "0" + solve(trie->next[0]);
	else if(!exist0 && exist1)bi = "0" + solve(trie->next[1]);
	else if (!exist0 && !exist1)return bi;
	else {
		string next_bi0 = "1" + solve(trie->next[0]);
		string next_bi1 = "1" + solve(trie->next[1]);
		if (binary_to_int(next_bi0) < binary_to_int(next_bi1))bi = next_bi0;
		else bi = next_bi1;
	}

	return bi;
}



int main()
{
	int n; cin >> n;
	vector<string>binaryA(n);
	for (int i = 0; i < n; i++) {
		int a; cin >> a;
		binaryA[i] = binary(a);
	}

	Trie* trie = new Trie();
	for (int i = 0; i < n; i++) {
		trie->insert(binaryA[i].data());
	}

	cout << binary_to_int(solve(trie)) << endl;

	return 0;
}