結果
問題 | No.130 XOR Minimax |
ユーザー |
|
提出日時 | 2016-10-21 17:03:55 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 325 ms / 5,000 ms |
コード長 | 889 bytes |
コンパイル時間 | 932 ms |
コンパイル使用メモリ | 80,768 KB |
実行使用メモリ | 98,688 KB |
最終ジャッジ日時 | 2024-09-12 22:41:12 |
合計ジャッジ時間 | 5,033 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#include <iostream> #include <vector> #include <memory> #define repeat(i,n) for (int i = 0; (i) < (n); ++(i)) using namespace std; struct tree_t { shared_ptr<tree_t> left, right; }; shared_ptr<tree_t> insert(shared_ptr<tree_t> t, int32_t x, int i) { if (not t) t = make_shared<tree_t>(); if (i == -1) return t; shared_ptr<tree_t> & nt = (x & (1 << i) ? t->right : t->left); nt = insert(nt, x, i-1); return t; } int dfs(shared_ptr<tree_t> const & t, int i) { return not t ? 0 : not t->left ? dfs(t->right, i-1) : not t->right ? dfs(t->left, i-1) : min(dfs(t->left, i-1), dfs(t->right, i-1)) + (1 << i); } int main() { int n; cin >> n; vector<int32_t> a(n); repeat (i,n) cin >> a[i]; shared_ptr<tree_t> root = nullptr; repeat (i,n) root = insert(root, a[i], 31); cout << dfs(root, 31) << endl; return 0; }