結果
問題 | No.130 XOR Minimax |
ユーザー |
![]() |
提出日時 | 2020-10-31 14:53:10 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 15 ms / 5,000 ms |
コード長 | 700 bytes |
コンパイル時間 | 12,880 ms |
コンパイル使用メモリ | 402,576 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-12 22:59:37 |
合計ジャッジ時間 | 14,891 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
use std::io::Read;fn calc(a: &[u32], k: u32) -> u32 {if a.len() <= 1 || k == 0 {return 0;}let k = k - 1;if (a[0] ^ a.last().unwrap()) >> k & 1 == 0 {calc(a, k)} else {let x = a.iter().position(|a| *a >> k & 1 == 1).unwrap();let p = a.split_at(x);std::cmp::min(calc(p.0, k), calc(p.1, k)) + (1 << k)}}fn run() {let mut s = String::new();std::io::stdin().read_to_string(&mut s).unwrap();let mut it = s.trim().split_whitespace();it.next();let mut a: Vec<u32> = it.map(|s| s.parse().unwrap()).collect();a.sort();let ans = calc(&a, 30);println!("{}", ans);}fn main() {run();}