結果
問題 | No.2977 Kth Xor Pair |
ユーザー | titia |
提出日時 | 2024-12-15 05:07:24 |
言語 | Rust (1.77.0 + proconio) |
結果 |
AC
|
実行時間 | 2,475 ms / 3,000 ms |
コード長 | 4,525 bytes |
コンパイル時間 | 13,096 ms |
コンパイル使用メモリ | 401,460 KB |
実行使用メモリ | 89,240 KB |
最終ジャッジ日時 | 2024-12-15 05:08:40 |
合計ジャッジ時間 | 57,180 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,816 KB |
testcase_01 | AC | 1 ms
6,816 KB |
testcase_02 | AC | 5 ms
6,820 KB |
testcase_03 | AC | 5 ms
6,816 KB |
testcase_04 | AC | 5 ms
6,816 KB |
testcase_05 | AC | 6 ms
6,816 KB |
testcase_06 | AC | 6 ms
6,816 KB |
testcase_07 | AC | 971 ms
51,984 KB |
testcase_08 | AC | 2,145 ms
77,980 KB |
testcase_09 | AC | 1,869 ms
76,332 KB |
testcase_10 | AC | 1,957 ms
73,616 KB |
testcase_11 | AC | 2,077 ms
75,488 KB |
testcase_12 | AC | 1,981 ms
73,664 KB |
testcase_13 | AC | 2,276 ms
87,044 KB |
testcase_14 | AC | 904 ms
52,296 KB |
testcase_15 | AC | 1,699 ms
73,676 KB |
testcase_16 | AC | 2,226 ms
85,196 KB |
testcase_17 | AC | 2,253 ms
85,624 KB |
testcase_18 | AC | 2,072 ms
80,296 KB |
testcase_19 | AC | 2,114 ms
89,240 KB |
testcase_20 | AC | 2,173 ms
89,060 KB |
testcase_21 | AC | 2,121 ms
86,636 KB |
testcase_22 | AC | 2,330 ms
83,744 KB |
testcase_23 | AC | 2,475 ms
82,588 KB |
testcase_24 | AC | 2,465 ms
84,128 KB |
testcase_25 | AC | 402 ms
80,808 KB |
testcase_26 | AC | 2,305 ms
86,092 KB |
testcase_27 | AC | 881 ms
9,756 KB |
testcase_28 | AC | 435 ms
9,880 KB |
testcase_29 | AC | 527 ms
9,756 KB |
testcase_30 | AC | 746 ms
9,760 KB |
testcase_31 | AC | 669 ms
9,884 KB |
testcase_32 | AC | 456 ms
6,820 KB |
testcase_33 | AC | 409 ms
6,816 KB |
testcase_34 | AC | 390 ms
6,816 KB |
testcase_35 | AC | 488 ms
6,816 KB |
ソースコード
use std::io; fn main() { let mut input = String::new(); io::stdin().read_line(&mut input).unwrap(); let mut iter = input.trim().split_whitespace(); let n: usize = iter.next().unwrap().parse().unwrap(); let k: usize = iter.next().unwrap().parse().unwrap(); input.clear(); io::stdin().read_line(&mut input).unwrap(); let a: Vec<i32> = input .trim() .split_whitespace() .map(|x| x.parse().unwrap()) .collect(); let r = n * (n - 1) / 2 - k + 1; let mut next_node_id0 = vec![-1]; let mut next_node_id1 = vec![-1]; let mut parent_id = vec![-1]; let mut depth = vec![0]; let mut count = vec![0]; let mut last = Vec::new(); let mut nodes_id = 1; for &num in &a { let mut now = 0; for i in (0..=31).rev() { let next = if num & (1 << i) == 0 { 0 } else { 1 }; if next == 0 { if next_node_id0[now] == -1 { next_node_id0[now] = nodes_id as i32; next_node_id0.push(-1); next_node_id1.push(-1); parent_id.push(now as i32); depth.push(depth[now] + 1); count.push(0); now = nodes_id; nodes_id += 1; } else { now = next_node_id0[now] as usize; } } else { if next_node_id1[now] == -1 { next_node_id1[now] = nodes_id as i32; next_node_id0.push(-1); next_node_id1.push(-1); parent_id.push(now as i32); depth.push(depth[now] + 1); count.push(0); now = nodes_id; nodes_id += 1; } else { now = next_node_id1[now] as usize; } } } count[now] += 1; last.push(now); } let mut count2 = vec![0; count.len()]; for &x in &last { let mut node = x as i32; while node != -1 { count2[node as usize] += 1; node = parent_id[node as usize]; } } let mut ok = 0; let mut ng = 2147483647; while ng > ok + 1 { let mid = (ok + ng) / 2; let mut total_count = 0; for &num in &a { if total_count / 2 >= r { break; } let mut now = 0; let mut current_count = 0; let mut flag = false; for dep in (0..=31).rev() { let x = next_node_id0[now]; let y = next_node_id1[now]; let num_bit = num & (1 << dep); let mid_bit = mid & (1 << dep); match (num_bit == 0, mid_bit == 0) { (true, true) => { if y != -1 { current_count += count2[y as usize]; } if x != -1 { now = x as usize; } else { flag = true; break; } } (true, false) => { if y != -1 { now = y as usize; } else { flag = true; break; } } (false, true) => { if x != -1 { current_count += count2[x as usize]; } if y != -1 { now = y as usize; } else { flag = true; break; } } (false, false) => { if x != -1 { now = x as usize; } else { flag = true; break; } } } } if !flag { current_count += count2[now]; } total_count += current_count; } if total_count / 2 >= r { ok = mid; } else { ng = mid; } } println!("{}", ok); }