提出 #53921848

---

ソースコード 拡げる

use proconio::input;

trait Bound<T> {
    fn lower_bound(&self, x: &T) -> usize;
    fn upper_bound(&self, x: &T) -> usize;
}

impl<T: PartialOrd> Bound<T> for [T] {
    fn lower_bound(&self, x: &T) -> usize {
        let (mut low, mut high) = (0, self.len());
        while low + 1 < high {
            let mid = (low + high) / 2;
            if self[mid] < *x {
                low = mid;
            } else {
                high = mid;
            }
        }
        if self[low] < *x {
            low + 1
        } else {
            low
        }
    }

    fn upper_bound(&self, x: &T) -> usize {
        let (mut low, mut high) = (0, self.len());
        while low + 1 < high {
            let mid = (low + high) / 2;
            if self[mid] <= *x {
                low = mid;
            } else {
                high = mid;
            }
        }
        if self[low] <= *x {
            low + 1
        } else {
            low
        }
    }
}

fn main() {
    input! {n:usize,cards:[(i32,i32);n]}
    let mut is_takahashi_win = vec![false; 1 << n];

    for i in 0..(1 << n) {
        let mut f = false;
        for j in 0..n {
            for k in (j + 1)..n {
                if ((i >> j & 1) == 1) && ((i >> k & 1) == 1) { // i,jに対応したカードが場にあるか判定
                    let mask = !((1 << j) | (1 << k)); // i,j以外が1のマスクを生成
                    if (cards[j].0 == cards[k].0 || cards[j].1 == cards[k].1)
                        && !is_takahashi_win[i & mask] // 場のカードにi,jを取り除くマスクをかける == 遷移後の状態を取得する
                    {
                        f = true
                    }
                }
            }
        }
        is_takahashi_win[i] = f;
    }

    println!(
        "{}",
        if *is_takahashi_win.last().unwrap() {
            "Takahashi"
        } else {
            "Aoki"
        }
    )
}

提出情報

ジャッジ結果