結果
問題 | No.1969 XOR Equation |
ユーザー |
![]() |
提出日時 | 2023-01-15 14:37:37 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 44 ms / 2,000 ms |
コード長 | 6,204 bytes |
コンパイル時間 | 13,190 ms |
コンパイル使用メモリ | 402,720 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-12-28 06:49:31 |
合計ジャッジ時間 | 15,621 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 36 |
ソースコード
// ---------- begin super slice ---------- pub trait SuperSlice { type Item; fn lower_bound(&self, key: &Self::Item) -> usize where Self::Item: Ord; fn lower_bound_by<F>(&self, f: F) -> usize where F: FnMut(&Self::Item) -> std::cmp::Ordering; fn lower_bound_by_key<K, F>(&self, key: &K, f: F) -> usize where K: Ord, F: FnMut(&Self::Item) -> K; fn upper_bound(&self, key: &Self::Item) -> usize where Self::Item: Ord; fn upper_bound_by<F>(&self, f: F) -> usize where F: FnMut(&Self::Item) -> std::cmp::Ordering; fn upper_bound_by_key<K, F>(&self, key: &K, f: F) -> usize where K: Ord, F: FnMut(&Self::Item) -> K; fn next_permutation(&mut self) -> bool where Self::Item: Ord; fn next_permutation_by<F>(&mut self, f: F) -> bool where F: FnMut(&Self::Item, &Self::Item) -> std::cmp::Ordering; fn prev_permutation(&mut self) -> bool where Self::Item: Ord; } impl<T> SuperSlice for [T] { type Item = T; fn lower_bound(&self, key: &Self::Item) -> usize where T: Ord, { self.lower_bound_by(|p| p.cmp(key)) } fn lower_bound_by<F>(&self, mut f: F) -> usize where F: FnMut(&Self::Item) -> std::cmp::Ordering, { self.binary_search_by(|p| f(p).then(std::cmp::Ordering::Greater)) .unwrap_err() } fn lower_bound_by_key<K, F>(&self, key: &K, mut f: F) -> usize where K: Ord, F: FnMut(&Self::Item) -> K, { self.lower_bound_by(|p| f(p).cmp(key)) } fn upper_bound(&self, key: &Self::Item) -> usize where T: Ord, { self.upper_bound_by(|p| p.cmp(key)) } fn upper_bound_by<F>(&self, mut f: F) -> usize where F: FnMut(&Self::Item) -> std::cmp::Ordering, { self.binary_search_by(|p| f(p).then(std::cmp::Ordering::Less)) .unwrap_err() } fn upper_bound_by_key<K, F>(&self, key: &K, mut f: F) -> usize where K: Ord, F: FnMut(&Self::Item) -> K, { self.upper_bound_by(|p| f(p).cmp(key)) } fn next_permutation(&mut self) -> bool where T: Ord, { self.next_permutation_by(|a, b| a.cmp(b)) } fn next_permutation_by<F>(&mut self, mut f: F) -> bool where F: FnMut(&Self::Item, &Self::Item) -> std::cmp::Ordering, { use std::cmp::Ordering::*; if let Some(x) = self.windows(2).rposition(|a| f(&a[0], &a[1]) == Less) { let y = self.iter().rposition(|b| f(&self[x], b) == Less).unwrap(); self.swap(x, y); self[(x + 1)..].reverse(); true } else { self.reverse(); false } } fn prev_permutation(&mut self) -> bool where T: Ord, { self.next_permutation_by(|a, b| a.cmp(b).reverse()) } } // ---------- end super slice ---------- // ---------- begin chmin, chmax ---------- pub trait ChangeMinMax { fn chmin(&mut self, x: Self) -> bool; fn chmax(&mut self, x: Self) -> bool; } impl<T: PartialOrd> ChangeMinMax for T { fn chmin(&mut self, x: Self) -> bool { *self > x && { *self = x; true } } fn chmax(&mut self, x: Self) -> bool { *self < x && { *self = x; true } } } // ---------- end chmin, chmax ---------- // ---------- begin scannner ---------- #[allow(dead_code)] mod scanner { use std::str::FromStr; pub struct Scanner<'a> { it: std::str::SplitWhitespace<'a>, } impl<'a> Scanner<'a> { pub fn new(s: &'a String) -> Scanner<'a> { Scanner { it: s.split_whitespace(), } } pub fn next<T: FromStr>(&mut self) -> T { self.it.next().unwrap().parse::<T>().ok().unwrap() } pub fn next_bytes(&mut self) -> Vec<u8> { self.it.next().unwrap().bytes().collect() } pub fn next_chars(&mut self) -> Vec<char> { self.it.next().unwrap().chars().collect() } pub fn next_vec<T: FromStr>(&mut self, len: usize) -> Vec<T> { (0..len).map(|_| self.next()).collect() } } } // ---------- end scannner ---------- use std::io::Write; fn main() { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); let mut sc = scanner::Scanner::new(&s); let out = std::io::stdout(); let mut out = std::io::BufWriter::new(out.lock()); run(&mut sc, &mut out); } fn run<W: Write>(sc: &mut scanner::Scanner, out: &mut std::io::BufWriter<W>) { let t: u32 = sc.next(); for _ in 0..t { let n: usize = sc.next(); let y: u64 = sc.next(); let a = sc.next_vec::<u64>(n); let mut a = a.into_iter().map(|a| (a, 0)).collect::<Vec<_>>(); a.sort_by_key(|p| p.1); let inf = std::u64::MAX / 2; let mut dp = vec![inf; n + 1]; dp[n] = 0; for i in 0..61 { let mut b = a .iter() .map(|a| (a.0, a.0 & ((2 << i) - 1))) .collect::<Vec<_>>(); b.sort_by_key(|p| p.1); let mut s = b.iter().fold(0, |s, b| s + (b.1 >> i & 1)); let y = y >> i & 1; let mut next = vec![inf; n + 1]; for (carry, dp) in dp.iter().enumerate().rev() { if carry < n { s += 1; } if *dp < inf { for v in 0..2 { let add = *dp + (v << i); let pos = b.lower_bound_by_key(&((2 << i) - add), |b| b.1); let xor = s + v * n as u64 - 2 * (n - pos) as u64; if xor & 1 == y { next[pos].chmin(add); } } } } dp = next; a = b; } if dp[n] < inf { writeln!(out, "{}", dp[n]).ok(); } else { writeln!(out, "-1").ok(); } } }