XOR MAX

2 secs 1024 MB

shinnshinn

Problem

Submissions

Test cases

Editorial

解説

$A_i$ を固定した時、 $A_i \oplus A_j$ を最大にする $A_j$ を効率的に探索します。

$A_i$ の $d$ ビットを上から下へ見ていきます。

最適な $A_j$ は $A_i$ とのxorを計算した時、 $d$ ビット目が1となるものです。

これは $d$ ビット目が1になる方が、その下のビットが全て1であっても結果として大きい値になるからです。

事前に数列をソートしておくと、各ビット位置に注目した場合にそのビットが０となる範囲と１となる範囲に分けることができます。

そして、適切な範囲を選択し各ビットごとに範囲を狭めていくことで解けます。

実装

xxxxxxxxxx
 
use proconio::*;
​
fn main() {
    input! {
        n: usize,
        mut a:[usize; n],
    }
    a.sort();
​
    let mut ans = 0;
    for i in 0..n-1 {
        let mut l = i+1;
        let mut r = n;
        for d in (0..30).rev() {
            if a[l]>>d & 1 == a[r-1]>>d & 1 {
                continue;
            }
            
            // dビット目が0となる範囲[l, ok]を求める
            let mut ok = l;
            let mut ng = r-1;
            while ng - ok > 1 {
                let mid = (ng+ok)/2;
                if a[mid] >> d & 1 == 0 {
                    ok = mid;
                } else {
                    ng = mid;
                }
            }
​
            if a[i]>>d & 1 == 1 {
                r = ng
            } else {
                l = ng;
            }
        }
​
        ans = ans.max(a[i] ^ a[l]);
    }
​
    println!("{}", ans);
}
​