https://atcoder.jp/contests/abc347/tasks/abc347_d
aとbとpopcount(C)で、Cの1をどちらに何個1にするか、0を何個1にするかが決まります。
// Popcount and XOR #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_line(&mut line).ok(); line.trim().parse().ok().unwrap() } fn read_vec<T: std::str::FromStr>() -> Vec<T> { read::<String>().split_whitespace() .map(|e| e.parse().ok().unwrap()).collect() } fn popcount(n: u64) -> u64 { if n == 0 { 0 } else { (n & 1) + popcount(n >> 1) } } fn b2d(bs: Vec<u64>) -> u64 { let mut d = 0; for i in (0..bs.len()).rev() { d = d * 2 + bs[i] } d } //////////////////// process //////////////////// fn read_input() -> (u64, u64, u64) { let v = read_vec(); let (a, b, C) = (v[0], v[1], v[2]); (a, b, C) } fn F(a: u64, b: u64, mut C: u64) -> Option<(u64, u64)> { let p = popcount(C); if a + b < p || a + p < b || b + p < a || (a + b) % 2 != p % 2 { return None } let mut bs1: Vec<u64> = vec![]; let mut bs2: Vec<u64> = vec![]; let mut c1: u64 = 0; let mut c3: u64 = 0; let c1_max = (a + p - b) / 2; let c3_max = a - c1_max; while C != 0 { let b1 = C & 1; C >>= 1; if b1 == 1 { if c1 < c1_max { bs1.push(1); bs2.push(0); c1 += 1 } else { bs1.push(0); bs2.push(1); } } else if c3 < c3_max { bs1.push(1); bs2.push(1); c3 += 1 } else { bs1.push(0); bs2.push(0) } } for _ in 0..a-c1-c3 { bs1.push(1); bs2.push(1) } if bs1.len() > 60 { return None } return Some((b2d(bs1), b2d(bs2))) } fn main() { let (a, b, C) = read_input(); match F(a, b, C) { Some((X, Y)) => println!("{} {}", X, Y), None => println!("-1") } }