結果

問題 No.2977 Kth Xor Pair
ユーザー ikdikd
提出日時 2024-12-01 19:26:45
言語 Rust
(1.77.0 + proconio)
結果
MLE  
実行時間 -
コード長 3,729 bytes
コンパイル時間 15,352 ms
コンパイル使用メモリ 380,720 KB
実行使用メモリ 821,668 KB
最終ジャッジ日時 2024-12-01 19:28:25
合計ジャッジ時間 92,734 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 MLE -
testcase_01 AC 1 ms
13,512 KB
testcase_02 AC 851 ms
348,192 KB
testcase_03 AC 869 ms
457,312 KB
testcase_04 AC 871 ms
347,556 KB
testcase_05 AC 852 ms
349,352 KB
testcase_06 AC 874 ms
348,324 KB
testcase_07 MLE -
testcase_08 MLE -
testcase_09 MLE -
testcase_10 MLE -
testcase_11 MLE -
testcase_12 MLE -
testcase_13 MLE -
testcase_14 MLE -
testcase_15 MLE -
testcase_16 MLE -
testcase_17 MLE -
testcase_18 MLE -
testcase_19 MLE -
testcase_20 MLE -
testcase_21 MLE -
testcase_22 MLE -
testcase_23 MLE -
testcase_24 MLE -
testcase_25 MLE -
testcase_26 MLE -
testcase_27 MLE -
testcase_28 MLE -
testcase_29 MLE -
testcase_30 MLE -
testcase_31 MLE -
testcase_32 TLE -
testcase_33 TLE -
testcase_34 TLE -
testcase_35 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

use proconio::input;

fn main() {
    input! {
        n: usize,
        k: usize,
        a: [u32; n],
    };

    let mut trie = vec![BinaryTrie::new(); n];
    for i in 0..n {
        for j in 0..i {
            trie[i].add(a[j]);
        }
    }

    // ● xor ▲ ≦ x を満たす組の個数
    let count_leq = |x: u32| -> usize {
        let mut res = 0;
        for i in 0..n {
            res += trie[i].query(a[i], x);
        }
        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, Clone)]
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
    }
}
0