AtCoder Beginner Contest 349 E

https://atcoder.jp/contests/abc349/tasks/abc349_e

状態数がしかなくて、深さも9しかないので、ふつうにメモ化すればよいです。

// Weighted Tic-Tac-Toe
#![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()
}


//////////////////// Color ////////////////////

#[derive(PartialEq, Copy, Clone)]
enum Color {
    White = 0,
    Red = 1,
    Blue = 2
}

impl Color {
    fn from_u32(n: u32) -> Color {
        match n {
            0 => Color::White,
            1 => Color::Red,
            _ => Color::Blue
        }
    }
}


//////////////////// State ////////////////////

struct State {
    C: [[Color; 3]; 3]
}

impl State {
    fn clone(&self) -> State {
        State { C: self.C.clone() }
    }
    
    fn exists_line(&self, color: Color) -> bool {
        for i in 0..3 {
            if (0..3).all(|j| self.C[i][j] == color) {
                return true
            }
        }
        for j in 0..3 {
            if (0..3).all(|i| self.C[i][j] == color) {
                return true
            }
        }
        if (0..3).all(|i| self.C[i][i] == color) {
            true
        }
        else if (0..3).all(|i| self.C[i][2-i] == color) {
            true
        }
        else {
            false
        }
    }
    
    fn wins_red(&self) -> bool {
        self.exists_line(Color::Red)
    }
    
    fn wins_blue(&self) -> bool {
        self.exists_line(Color::Blue)
    }
    
    fn num_remained_cells(&self) -> usize {
        self.C.iter().flatten().filter(|&c| *c == Color::White).count()
    }
    
    fn is_finished(&self) -> bool {
        self.num_remained_cells() == 0
    }
    
    fn turn(&self) -> Color {
        let n = self.num_remained_cells();
        if n % 2 == 1 { Color::Red } else { Color::Blue }
    }
    
    fn encode(&self) -> u32 {
        let mut s: u32 = 0;
        for i in (0..3).rev() {
            for j in (0..3).rev() {
                s = s * 3 + (self.C[i][j] as u32)
            }
        }
        s
    }
    
    fn decode(mut s: u32) -> State {
        let mut C: [[Color; 3]; 3] = [[Color::White; 3]; 3];
        for i in 0..3 {
            for j in 0..3 {
                C[i][j] = Color::from_u32(s % 3);
                s /= 3
            }
        }
        State { C }
    }
    
    fn nexts(&self) -> Vec<u32> {
        let mut states: Vec<u32> = vec![];
        let color = self.turn();
        for i in 0..3 {
            for j in 0..3 {
                if self.C[i][j] == Color::White {
                    let mut s = self.clone();
                    s.C[i][j] = color;
                    states.push(s.encode())
                }
            }
        }
        states
    }
}


//////////////////// Board ////////////////////

struct Board {
    A: [[i64; 3]; 3],
    win_vec: Vec<i32>
}

impl Board {
    fn wins_core(&mut self, s: u32) -> bool {
        let state = State::decode(s);
        if state.wins_red() {
            true
        }
        else if state.wins_blue() {
            false
        }
        else if state.is_finished() {
            let mut sum_red: i64 = 0;
            let mut sum_blue: i64 = 0;
            for i in 0..3 {
                for j in 0..3 {
                    if state.C[i][j] == Color::Red {
                        sum_red += self.A[i][j]
                    }
                    else {
                        sum_blue += self.A[i][j]
                    }
                }
            }
            sum_red > sum_blue
        }
        else if state.turn() == Color::Red {
            state.nexts().into_iter().any(|s1| self.wins(s1))
        }
        else {
            !state.nexts().into_iter().any(|s1| !self.wins(s1))
        }
    }
    
    fn wins(&mut self, s: u32) -> bool {
        if self.win_vec[s as usize] == 0 {
            let b = self.wins_core(s);
            self.win_vec[s as usize] = if b { 1 } else { 2 }
        }
        self.win_vec[s as usize] == 1
    }
    
    fn read_row() -> [i64; 3] {
        let v: Vec<i64> = read_vec();
        [v[0], v[1], v[2]]
    }
    
    fn read() -> Board {
        let A: [[i64; 3]; 3] = [Board::read_row(),
                                Board::read_row(),
                                Board::read_row()];
        let N = 3usize.pow(9);
        let win_vec: Vec<i32> = vec![0; N];
        Board { A, win_vec }
    }
}


//////////////////// process ////////////////////

fn F(mut board: Board) -> bool {
    board.wins(0)
}

fn main() {
    let board = Board::read();
    let b = F(board);
    println!("{}", if b { "Takahashi" } else { "Aoki" })
}

AtCoder Beginner Contest 349 D

https://atcoder.jp/contests/abc349/tasks/abc349_d

Rを超えないようにできるだけ飛べばよいです。

// Divide Interval
#![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()
}


//////////////////// process ////////////////////

fn read_input() -> (u64, u64) {
    let v = read_vec();
    let (L, R) = (v[0], v[1]);
    (L, R)
}

fn print_intervals(intervals: Vec<(u64, u64)>) {
    println!("{}", intervals.len());
    for (l, r) in intervals.into_iter() {
        println!("{} {}", l, r)
    }
}

fn next(l: u64, R: u64) -> u64 {
    let mut d: u64 = 1;
    loop {
        if l + d > R {
            d >>= 1;
            break
        }
        else if l % d != 0 {
            d >>= 1;
            break
        }
        else {
            d <<= 1
        }
    }
    l + d
}

fn F(L: u64, R: u64) -> Vec<(u64, u64)> {
    let mut intervals: Vec<(u64, u64)> = vec![];
    let mut l = L;
    while l < R {
        let r = next(l, R);
        intervals.push((l, r));
        l = r
    }
    intervals
}

fn main() {
    let (L, R) = read_input();
    let intervals = F(L, R);
    print_intervals(intervals)
}

AtCoder Beginner Contest 348 D

https://atcoder.jp/contests/abc348/tasks/abc348_d

ふつうにQueueを使ってたどればよいです。

// Medicines on Grid
#![allow(non_snake_case)]

use std::collections::VecDeque;


//////////////////// 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 YesNo(b: bool) -> String {
    return if b { "Yes" } else { "No" }.to_string()
}


//////////////////// Table ////////////////////

type Point = (usize, usize);

struct Table {
    H: usize,
    W: usize,
    cells: Vec<Vec<(char, i32)>>
}

impl Table {
    fn is_obstacle(&self, pt: Point) -> bool {
        self.cells[pt.0][pt.1].0 == '#'
    }
    
    fn get_medicine(&self, pt: Point) -> i32 {
        self.cells[pt.0][pt.1].1
    }
    
    fn nexts(&self, pt: Point) -> Vec<Point> {
        let (x, y) = pt;
        let mut pts: Vec<Point> = vec![];
        if x > 0 && !self.is_obstacle((x-1, y)) {
            pts.push((x-1, y))
        }
        if x < self.H - 1 && !self.is_obstacle((x+1, y)) {
            pts.push((x+1, y))
        }
        if y > 0 && !self.is_obstacle((x, y-1)) {
            pts.push((x, y-1))
        }
        if y < self.W - 1 && !self.is_obstacle((x, y+1)) {
            pts.push((x, y+1))
        }
        pts
    }
    
    fn find(&self, c: char) -> Option<Point> {
        for (x, v) in self.cells.iter().enumerate() {
            for (y, c1) in v.iter().enumerate() {
                if c1.0 == c {
                    return Some((x, y))
                }
            }
        }
        None
    }
    
    fn read() -> Table {
        let v: Vec<usize> = read_vec();
        let (H, W) = (v[0], v[1]);
        let mut cells: Vec<Vec<(char, i32)>> = (0..H).map(|_| 
                                                        read::<String>().
                                                        chars().
                                                        map(|c| (c, 0)).
                                                        collect::<Vec<_>>()
                                                    ).collect();
        
        let N: usize = read();
        for _ in 0..N {
            let w: Vec<usize> = read_vec();
            let (R, C) = (w[0]-1, w[1]-1);
            let E = w[2] as i32;
            cells[R][C].1 = E
        }
        
        Table { H, W, cells }
    }
}


//////////////////// process ////////////////////

fn F(table: Table) -> bool {
    let mut energies = vec![vec![0; table.W]; table.H];
    let mut queue: VecDeque<(Point, i32)> = VecDeque::new();
    let S = table.find('S').unwrap();
    let T = table.find('T').unwrap();
    queue.push_back((S, table.get_medicine(S)));
    while let Some((pt, energy)) = queue.pop_front() {
        if energy == 0 || energy < energies[pt.0][pt.1] {
            continue
        }
        for pt1 in table.nexts(pt).into_iter() {
            if pt1 == T {
                return true
            }
            let m = table.get_medicine(pt1);
            let e = std::cmp::max(m, energy - 1);
            if e > energies[pt1.0][pt1.1] {
                energies[pt1.0][pt1.1] = e;
                queue.push_back((pt1, e))
            }
        }
    }
    false
}

fn main() {
    let table = Table::read();
    println!("{}", YesNo(F(table)))
}

MojoでProject Euler 27

https://projecteuler.net/problem=27

素数の判定をどれくらい大きさまで行っていいか分からないので、ナイーブに判定してメモ化してみました。
MojoではDictを使えるようになりました。

from collections import Dict

fn main() raises:
    var d = Dict[String, Int]()
    d["a"] = 1
    print(d["a"])       # 1
    print("a" in d)     # True

なので、これをメモ化に使おうとしましたが、

from collections import Dict

var memo = Dict[String, Int]()
fn f(s: String) raises -> Int:
    if s in memo:
        return memo[s]
    elif s == "a":
        memo[s] = 1
        return 1
    else:
        memo[s] = 2
        return 2

fn main() raises:
    print(f("a"))
    print(f("b"))
    print(f("a"))
    print(f("b"))

このテストコードはなぜか落ちます。どうも現状Dictをグローバルな変数にはできないっぽいです。仕方なく、DynamicVectorを使いました。

from collections import Dict
from math import min
import sys


#################### library ####################

def div_pow(n: Int, d: Int) -> Tuple[Int, Int]:
    var m = n
    var e = 0
    while m % d == 0:
        e += 1
        m //= d
    return (e, m)


#################### process ####################

fn calc_min_b(a: Int, L: Int) -> Int:
    if a > 0:
        return 2
    elif -a < L * 2:
        var n = a // 2
        return 2 - (n * n + a * n)
    else:
        return 2 - (L * L + a * L)

var primes = DynamicVector[Int]()
def is_prime(n: Int) -> Bool:
    if n < 2:
        return False
    elif n < primes.size and primes[n] != -1:
        return primes[n] == 1
    
    var b = True
    for p in range(2, n+1):
        if p * p > n:
            break
        elif n % p == 0:
            b = False
            break
    
    if n >= primes.size:
        for m in range(primes.size, n+1):
            primes.push_back(-1)
    primes[n] = 1 if b else 0
    return b

def length(a: Int, b: Int) -> Int:
    var n = 0
    while True:
        m = n * n + a * n + b
        if not is_prime(m):
            break
        n += 1
    return n

fn f(N: Int) raises -> Int:
    var max_length = 0
    var max_product = 0
    for a in range(-N+1, N):
        var min_b = calc_min_b(a, max_length)
        for b in range(min_b, N+1):
            var l = length(a, b)
            if l > max_length:
                max_length = l
                max_product = a * b
                print(a, b, l)
    return max_product

fn main() raises:
    var args = sys.argv()
    var N = atol(args[1])
    print(f(N))

AtCoder Beginner Contest 347 F

https://atcoder.jp/contests/abc347/tasks/abc347_f

3つの正方形は、6通りの配置があって、2つの座標を定めればある長方形の範囲最大の和になります。
Rustなのに時間的にかなり際どいです。木を辿らずにいきなり値を取れるところは取るようにして、やっと通りました。

// Set Add Query
#![allow(non_snake_case)]

use std::cmp::max;


//////////////////// 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()
}


//////////////////// Segment Tree ////////////////////

type Val = i64;
type Range = (usize, usize);

struct SegmentTree {
    n: usize,
    m: usize,
    v: Vec<Val>,
}

impl SegmentTree {
    fn max(&self, rng: Range) -> Val {
        if rng == (0, self.m) {
            self.v[0]
        }
        else if rng.0 == rng.1 - 1 {
            self.v[rng.0+self.n-1]
        }
        else {
            self.max_core(rng, 0, self.n, 0)
        }
    }
    
    fn max_core(&self, rng: Range, first: usize, last: usize, i: usize) -> Val {
        if rng.0 <= first && last <= rng.1 {
            self.v[i]
        }
        else {
            let mid = (first + last) / 2;
            if rng.1 <= mid {
                self.max_core(rng, first, mid, i*2+1)
            }
            else if rng.0 >= mid {
                self.max_core(rng, mid, last, i*2+2)
            }
            else {
                max(self.max_core(rng, first, mid, i*2+1),
                    self.max_core(rng, mid, last, i*2+2))
            }
        }
    }
    
    fn ceil_two_pow(n: usize) -> usize {
        if n == 1 { 1 } else { SegmentTree::ceil_two_pow((n+1)/2) * 2 }
    }
    
    fn create(a: &Vec<Val>) -> SegmentTree {
        let m = a.len();
        let n = SegmentTree::ceil_two_pow(m);
        let mut v: Vec<Val> = vec![0; n*2-1];
        for i in n-1..n+m-1 {
            v[i] = a[i+1-n]
        }
        for i in (0..n-1).rev() {
            v[i] = max(v[i*2+1], v[i*2+2])
        }
        SegmentTree { n, m, v }
    }
    
    fn max_segment(s1: &SegmentTree, s2: &SegmentTree) -> SegmentTree {
        let v: Vec<Val> = s1.v.iter().zip(s2.v.iter()).
                                map(|(&a, &b)| max(a, b)).collect();
        SegmentTree { n: s1.n, m: s1.m, v }
    }
}


//////////////////// Segment Tree 2D ////////////////////

struct SegmentTree2D {
    n: usize,
    m: usize,
    v: Vec<SegmentTree>,
}

impl SegmentTree2D {
    fn max(&self, rng1: Range, rng2: Range) -> Val {
        if rng1 == (0, self.m) {
            self.v[0].max(rng2)
        }
        else if rng1.0 == rng1.1 - 1 {
            self.v[rng1.0+self.n-1].max(rng2)
        }
        else {
            self.max_core(rng1, rng2, 0, self.n, 0)
        }
    }
    
    fn max_core(&self, rng1: Range, rng2: Range,
                        first: usize, last: usize, i: usize) -> Val {
        if rng1.0 <= first && last <= rng1.1 {
            self.v[i].max(rng2)
        }
        else {
            let mid = (first + last) / 2;
            if rng1.1 <= mid {
                self.max_core(rng1, rng2, first, mid, i*2+1)
            }
            else if rng1.0 >= mid {
                self.max_core(rng1, rng2, mid, last, i*2+2)
            }
            else {
                max(self.max_core(rng1, rng2, first, mid, i*2+1),
                    self.max_core(rng1, rng2, mid, last, i*2+2))
            }
        }
    }
    
    fn row_max(&self, i: usize) -> i64 {
        self.v[i+self.n-1].v[0]
    }
    
    fn column_max(&self, j: usize) -> i64 {
        let tree = &self.v[0];
        tree.v[j+tree.n-1]
    }
    
    fn create(A: &Vec<Vec<Val>>) -> SegmentTree2D {
        let m = A.len();
        let n = SegmentTree::ceil_two_pow(m);
        let mut v: Vec<SegmentTree> = vec![];
        for _ in 0..n*2-1 {
            // 仮のSegmentTreeを登録
            let w: Vec<Val> = vec![0];
            v.push(SegmentTree { n: 1, m, v: w })
        }
        for i in n-1..n+m-1 {
            v[i] = SegmentTree::create(&A[i+1-n])
        }
        for i in n+m-1..n*2-1 {
            v[i] = SegmentTree::create(&vec![0; n*2-1])
        }
        for i in (0..n-1).rev() {
            v[i] = SegmentTree::max_segment(&v[i*2+1], &v[i*2+2])
        }
        SegmentTree2D { n, m, v }
    }
}


//////////////////// Matrix ////////////////////

type Matrix = Vec<Vec<i64>>;


//////////////////// Table ////////////////////

struct Table {
    N: usize,
    M: usize,
    tree: SegmentTree2D
}

impl Table {
    fn max(&self) -> i64 {
        let v: Vec<i64> = vec![self.max1(), self.max2(), self.max3(),
                               self.max4(), self.max5(), self.max6()];
        v.into_iter().fold(0, |x, y| max(x, y))
    }
    
    // 1 2
    //  3
    fn max1(&self) -> i64 {
        let mut max_value: i64 = 0;
        for i in self.M..self.N-self.M+1 {      // 3の縦座標
            for j in 0..self.N-self.M*2+1 {     // 1の横座標
                let max1 = self.tree.max(self.above(i), (j, j+1));
                let max2 = self.tree.max(self.above(i), self.right(j));
                let max3 = self.tree.row_max(i);
                max_value = max(max_value, max1 + max2 + max3);
            }
        }
        max_value
    }
    
    //  3
    // 1 2
    fn max2(&self) -> i64 {
        let mut max_value: i64 = 0;
        for i in 0..self.N-self.M*2+1 {         // 3の縦座標
            for j in 0..self.N-self.M*2+1 {     // 1の横座標
                let max1 = self.tree.max(self.below(i), (j, j+1));
                let max2 = self.tree.max(self.below(i), self.right(j));
                let max3 = self.tree.row_max(i);
                max_value = max(max_value, max1 + max2 + max3);
            }
        }
        max_value
    }
    
    // 1
    //   2
    // 3
    fn max3(&self) -> i64 {
        let mut max_value: i64 = 0;
        for i in 0..self.N-self.M*2+1 {         // 1の縦座標
            for j in self.M..self.N-self.M+1 {  // 2の横座標
                let max1 = self.tree.max((i, i+1), self.left(j));
                let max2 = self.tree.column_max(j);
                let max3 = self.tree.max(self.below(i), self.left(j));
                max_value = max(max_value, max1 + max2 + max3);
            }
        }
        max_value
    }
    
    //   1
    // 2
    //   3
    fn max4(&self) -> i64 {
        let mut max_value: i64 = 0;
        for i in 0..self.N-self.M*2+1 {         // 1の縦座標
            for j in 0..self.N-self.M*2+1 {     // 2の横座標
                let max1 = self.tree.max((i, i+1), self.right(j));
                let max2 = self.tree.column_max(j);
                let max3 = self.tree.max(self.below(i), self.right(j));
                max_value = max(max_value, max1 + max2 + max3);
            }
        }
        max_value
    }
    
    // 1 2 3
    fn max5(&self) -> i64 {
        let mut max_value: i64 = 0;
        for j in self.M..self.N-self.M*2+1 {    // 真ん中の横座標
            let max1 = self.tree.max((0, self.N-self.M+1), self.left(j));
            let max2 = self.tree.max((0, self.N-self.M+1), (j, j+1));
            let max3 = self.tree.max((0, self.N-self.M+1), self.right(j));
            max_value = max(max_value, max1 + max2 + max3);
        }
        max_value
    }
    
    // 1
    // 2
    // 3
    fn max6(&self) -> i64 {
        let mut max_value: i64 = 0;
        for i in self.M..self.N-self.M*2+1 {    // 真ん中の縦座標
            let max1 = self.tree.max(self.above(i), (0, self.N-self.M+1));
            let max2 = self.tree.row_max(i);
            let max3 = self.tree.max(self.below(i), (0, self.N-self.M+1));
            max_value = max(max_value, max1 + max2 + max3);
        }
        max_value
    }
    
    fn above(&self, i: usize) -> Range {
        (0, i-self.M+1)
    }
    
    fn below(&self, i: usize) -> Range {
        (i+self.M, self.N-self.M+1)
    }
    
    fn left(&self, j: usize) -> Range {
        (0, j-self.M+1)
    }
    
    fn right(&self, j: usize) -> Range {
        (j+self.M, self.N-self.M+1)
    }
    
    fn accumulate(A: &Matrix) -> Matrix {
        let N = A.len();
        let mut B: Matrix = vec![vec![0; N+1]; N+1];
        for i in 0..N {
            for j in 0..N {
                B[i+1][j+1] = B[i+1][j] + B[i][j+1] - B[i][j] + A[i][j]
            }
        }
        B
    }
    
    fn make_sum_matrix(M: usize, B: &Matrix) -> Matrix {
        let N = B.len() - 1;
        let L = N - M + 1;
        let mut C: Matrix = vec![vec![0; L]; L];
        for i in 0..L {
            for j in 0..L {
                C[i][j] = B[i+M][j+M] - B[i][j+M] - B[i+M][j] + B[i][j]
            }
        }
        C
    }
}


//////////////////// process ////////////////////

fn read_input() -> (usize, Matrix) {
    let v = read_vec();
    let (N, M) = (v[0], v[1]);
    let A: Matrix = (0..N).map(|_| read_vec::<i64>()).collect();
    (M, A)
}

fn make_table(M: usize, A: Matrix) -> Table {
    let N = A.len();
    let B = Table::accumulate(&A);
    let C = Table::make_sum_matrix(M, &B);
    let tree = SegmentTree2D::create(&C);
    Table { N, M, tree }
}

fn F(M: usize, A: Matrix) -> i64 {
    let table = make_table(M, A);
    table.max()
}

fn main() {
    let (M, A) = read_input();
    println!("{}", F(M, A))
}

AtCoder Beginner Contest 347 E

https://atcoder.jp/contests/abc347/tasks/abc347_e

時系列でSの大きさを記録します。実際には累積和をVecにします。

// Set Add Query
#![allow(non_snake_case)]

use std::collections::HashMap;


//////////////////// 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()
}


//////////////////// process ////////////////////

fn read_input() -> (usize, Vec<usize>) {
    let v = read_vec();
    let N = v[0];
    let X_: Vec<usize> = read_vec();
    let X: Vec<usize> = X_.into_iter().map(|x| x - 1).collect();
    (N, X)
}

fn F(N: usize, X: Vec<usize>) -> Vec<usize> {
    let mut A: Vec<usize> = vec![0; N];
    let mut acc: Vec<usize> = vec![0];
    let mut dic: HashMap<usize, usize> = HashMap::new();
    for (p, x) in X.into_iter().enumerate() {
        if dic.contains_key(&x) {
            let q = dic.get(&x).unwrap();
            A[x] += acc[p] - acc[*q];
            dic.remove(&x);
        }
        else {
            dic.insert(x, p);
        }
        acc.push(acc.last().unwrap() + dic.len())
    }
    
    for (x, p) in dic.into_iter() {
        A[x] += acc.last().unwrap() - acc[p]
    }
    A
}

fn main() {
    let (N, X) = read_input();
    let A = F(N, X);
    println!("{}", A.into_iter().map(|a| a.to_string()).
                                    collect::<Vec<_>>().join(" "))
}

AtCoder Beginner Contest 347 D

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")
    }
}