#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
• 実行時間: 249 ms / 5,000 ms
• コード長: 1,582 bytes
• コンパイル時間: 964 ms
• コンパイル使用メモリ: 66,376 KB
• 実行使用メモリ: 61,696 KB
• 最終ジャッジ日時: 2024-09-12 22:44:54
• 合計ジャッジ時間: 4,839 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	126 ms; 28,160 KB
testcase_01	AC	2 ms; 6,816 KB
testcase_02	AC	2 ms; 6,940 KB
testcase_03	AC	2 ms; 6,940 KB
testcase_04	AC	77 ms; 14,208 KB
testcase_05	AC	107 ms; 14,208 KB
testcase_06	AC	107 ms; 20,340 KB
testcase_07	AC	120 ms; 20,224 KB
testcase_08	AC	235 ms; 61,696 KB
testcase_09	AC	21 ms; 6,940 KB
testcase_10	AC	31 ms; 8,064 KB
testcase_11	AC	98 ms; 16,896 KB
testcase_12	AC	11 ms; 6,940 KB
testcase_13	AC	81 ms; 14,592 KB
testcase_14	AC	249 ms; 50,560 KB
testcase_15	AC	4 ms; 6,944 KB
testcase_16	AC	173 ms; 37,120 KB
testcase_17	AC	182 ms; 38,272 KB
testcase_18	AC	196 ms; 40,960 KB
testcase_19	AC	232 ms; 47,744 KB
testcase_20	AC	113 ms; 25,728 KB
testcase_21	AC	247 ms; 50,176 KB
testcase_22	AC	52 ms; 13,952 KB
testcase_23	AC	16 ms; 6,940 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;
}