Submission #3784640
Source Code Expand
use std::cmp::Ordering; fn read<T: std::str::FromStr>() -> T { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().parse().ok().unwrap() } fn read_vec<T: std::str::FromStr>() -> Vec<T> { read::<String>() .split_whitespace() .map(|e| e.parse().ok().unwrap()) .collect() } pub trait BinarySearch<T> { fn lower_bound(&self, &T) -> usize; fn upper_bound(&self, &T) -> usize; } impl<T: Ord> BinarySearch<T> for [T] { fn lower_bound(&self, x: &T) -> usize { let mut low = 0; let mut high = self.len(); while low != high { let mid = (low + high) / 2; match self[mid].cmp(x) { Ordering::Less => { low = mid + 1; } Ordering::Equal | Ordering::Greater => { high = mid; } } } low } fn upper_bound(&self, x: &T) -> usize { let mut low = 0; let mut high = self.len(); while low != high { let mid = (low + high) / 2; match self[mid].cmp(x) { Ordering::Less | Ordering::Equal => { low = mid + 1; } Ordering::Greater => { high = mid; } } } low } } fn main() { let _: usize = read(); let a: Vec<u64> = read_vec(); let b: Vec<u64> = read_vec(); let mut ans = 0; for c in 1..29 { let c = 2u64.pow(c); let half_c = c / 2; let temp_a = a.iter().map(|x| x % c).collect::<Vec<_>>(); let mut temp_b = b.iter().map(|x| x % c).collect::<Vec<_>>(); temp_b.sort(); let mut counts = 0; for a_num in temp_a { if a_num < half_c { let lb = temp_b.lower_bound(&(half_c - a_num)); let ub = temp_b.lower_bound(&(c - a_num)); counts += ub - lb; } else if a_num == half_c { let lb = temp_b.lower_bound(&half_c); counts += lb; } else { let lb = temp_b.lower_bound(&(c - a_num)); let ub = temp_b.lower_bound(&(c + half_c - a_num)); counts += temp_b.len() - ub + lb; } } if counts % 2 == 1 { ans += half_c; } } println!("{:?}", ans); }
Submission Info
Submission Time | |
---|---|
Task | D - Two Sequences |
User | ryoryoryo111 |
Language | Rust (1.15.1) |
Score | 0 |
Code Size | 2539 Byte |
Status | WA |
Exec Time | 1790 ms |
Memory | 14008 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 500 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | example_0, example_1, example_2, example_3 |
All | N100000_0, N100000_1, N150000_0, N150000_1, N200000_0, N200000_1, N200000_ex_0, N200000_ex_1, example_0, example_1, example_2, example_3, rand_0, rand_1, smallrand_0, smallrand_1 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
N100000_0 | AC | 779 ms | 10036 KB |
N100000_1 | WA | 778 ms | 9928 KB |
N150000_0 | AC | 1255 ms | 11480 KB |
N150000_1 | WA | 1251 ms | 11768 KB |
N200000_0 | AC | 1790 ms | 13384 KB |
N200000_1 | WA | 1788 ms | 13388 KB |
N200000_ex_0 | AC | 1710 ms | 13784 KB |
N200000_ex_1 | AC | 1707 ms | 14008 KB |
example_0 | AC | 2 ms | 4352 KB |
example_1 | AC | 2 ms | 4352 KB |
example_2 | AC | 2 ms | 4352 KB |
example_3 | AC | 2 ms | 4352 KB |
rand_0 | AC | 32 ms | 4352 KB |
rand_1 | WA | 72 ms | 4352 KB |
smallrand_0 | AC | 2 ms | 4352 KB |
smallrand_1 | AC | 2 ms | 4352 KB |