結果
問題 | No.2977 Kth Xor Pair |
ユーザー |
![]() |
提出日時 | 2024-12-01 19:14:01 |
言語 | Rust (1.83.0 + proconio) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,643 bytes |
コンパイル時間 | 13,460 ms |
コンパイル使用メモリ | 378,876 KB |
実行使用メモリ | 99,072 KB |
最終ジャッジ日時 | 2024-12-01 19:15:57 |
合計ジャッジ時間 | 110,829 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 14 TLE * 20 |
ソースコード
use proconio::input;fn main() {input! {n: usize,k: usize,a: [u32; n],};// ● xor ▲ ≦ x を満たす組の個数let count_leq = |x: u32| -> usize {let mut res = 0;let mut trie = BinaryTrie::new();for &a in &a {res += trie.query(a, x);trie.add(a);}res};if count_leq(0) >= k {println!("0");return;}// ● xor ▲ ≦ ok が k 個以上あるlet mut ng = 0;let mut ok = u32::MAX / 2;while ok - ng > 1 {let mid = (ok + ng) / 2;if count_leq(mid) >= k {ok = mid;} else {ng = mid;}}println!("{}", ok);}#[derive(Debug, Clone)]struct Node {size: usize,children: [Option<Box<Node>>; 2],}impl Node {fn new() -> Self {Self {size: 0,children: [None, None],}}}#[derive(Debug)]struct BinaryTrie {root: Node,}impl BinaryTrie {fn new() -> Self {Self { root: Node::new() }}fn add(&mut self, value: u32) {let mut node = &mut self.root;node.size += 1;for i in (0..u32::BITS).rev() {let index = (value >> i & 1) as usize;node = node.children[index].get_or_insert_with(|| Box::new(Node::new()));node.size += 1;}}fn query(&self, a: u32, x: u32) -> usize {// fn f(node: &Node, k: u32, a: u32, x: u32) -> usize {// if k == 0 {// let a_k = (a >> k & 1) as usize;// if x >> k & 1 == 0 {// match &node.children[a_k] {// Some(n) => n.size,// None => 0,// }// } else {// match &node.children {// [Some(n), Some(m)] => n.size + m.size,// [Some(n), None] => n.size,// [None, Some(n)] => n.size,// [None, None] => 0,// }// }// } else {// let a_k = (a >> k & 1) as usize;// if x >> k & 1 == 0 {// match &node.children[a_k] {// Some(n) => f(n, k - 1, a, x),// None => 0,// }// } else {// let c = match &node.children[a_k] {// Some(n) => n.size,// None => 0,// };// let d = match &node.children[a_k ^ 1] {// Some(n) => f(n, k - 1, a, x),// None => 0,// };// c + d// }// }// }// f(&self.root, u32::BITS - 1, a, x)let mut node = &self.root;let mut res = 0;for k in (0..u32::BITS).rev() {let a_k = (a >> k & 1) as usize;if x >> k & 1 == 0 {match &node.children[a_k] {Some(n) => node = n,None => return res,}} else {res += match &node.children[a_k] {Some(n) => n.size,None => 0,};match &node.children[a_k ^ 1] {Some(n) => node = n,None => return res,}}}res + node.size}}