Submission #5028959


Source Code Expand

Copy
use std::collections::{BTreeMap, BTreeSet};

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let n: usize = sc.read();
    let l: u64 = sc.read();
    let mut trie = Trie {
        nodes: vec![[0; 2]],
    };
    for _ in 0..n {
        let s: Vec<usize> = sc
            .chars()
            .into_iter()
            .map(|c| c as usize - '0' as usize)
            .collect();
        trie.add(&s, 0, 0);
    }

    let mut results = vec![];
    trie.traverse(0, &mut results, l);
    println!(
        "{}",
        if results
            .into_iter()
            .map(|h| 1 << h.trailing_zeros())
            .fold(0, |xor, x| xor ^ x)
            == 0
        {
            "Bob"
        } else {
            "Alice"
        }
    );
}

struct Trie {
    nodes: Vec<[usize; 2]>,
}

impl Trie {
    fn add(&mut self, s: &[usize], pos: usize, cur: usize) {
        if pos == s.len() {
            return;
        }
        if self.nodes[cur][s[pos]] == 0 {
            self.nodes[cur][s[pos]] = self.nodes.len();
            self.nodes.push([0; 2]);
        }
        let cur = self.nodes[cur][s[pos]];
        self.add(s, pos + 1, cur);
    }

    fn traverse(&self, cur: usize, results: &mut Vec<u64>, height: u64) {
        let (a, b) = (self.nodes[cur][0], self.nodes[cur][1]);
        if a == 0 && b == 0 {
            return;
        }
        if a == 0 || b == 0 {
            results.push(height);
        }
        if a != 0 {
            self.traverse(a, results, height - 1);
        }
        if b != 0 {
            self.traverse(b, results, height - 1);
        }
    }
}

fn grundy(l: usize, map: &mut BTreeMap<usize, usize>) -> usize {
    match map.get(&l) {
        Some(&x) => x,
        None => {
            let mut set = BTreeSet::new();
            for i in 1..(l + 1) {
                let mut g = 0;
                for j in 1..i {
                    g ^= grundy(l - j, map);
                }
                set.insert(g);
            }
            let g = (0..).find(|x| !set.contains(x)).unwrap();
            map.insert(l, g);
            g
        }
    }
}

pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

Submission Info

Submission Time
Task E - Prefix-free Game
User kenkoooo
Language Rust (1.15.1)
Score 700
Code Size 3058 Byte
Status
Exec Time 11 ms
Memory 17788 KB

Compile Error

warning: function is never used: `grundy`, #[warn(dead_code)] on by default
  --> ./Main.rs:71:1
   |
71 | fn grundy(l: usize, map: &mut BTreeMap<usize, usize>) -> usize {
   | ^

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 0_04.txt, 0_05.txt
All 700 / 700 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 0_04.txt, 0_05.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt, 1_47.txt, 1_48.txt, 1_49.txt, 1_50.txt, 1_51.txt, 1_52.txt, 1_53.txt
Case Name Status Exec Time Memory
0_00.txt 2 ms 4352 KB
0_01.txt 2 ms 4352 KB
0_02.txt 2 ms 4352 KB
0_03.txt 2 ms 4352 KB
0_04.txt 2 ms 4352 KB
0_05.txt 2 ms 4352 KB
1_00.txt 2 ms 4352 KB
1_01.txt 2 ms 4352 KB
1_02.txt 2 ms 4352 KB
1_03.txt 2 ms 4352 KB
1_04.txt 2 ms 4352 KB
1_05.txt 2 ms 4352 KB
1_06.txt 11 ms 17788 KB
1_07.txt 9 ms 13052 KB
1_08.txt 8 ms 11004 KB
1_09.txt 9 ms 13052 KB
1_10.txt 9 ms 13052 KB
1_11.txt 4 ms 4352 KB
1_12.txt 5 ms 4352 KB
1_13.txt 5 ms 4352 KB
1_14.txt 7 ms 4352 KB
1_15.txt 7 ms 4352 KB
1_16.txt 7 ms 4352 KB
1_17.txt 7 ms 4352 KB
1_18.txt 7 ms 4352 KB
1_19.txt 7 ms 4352 KB
1_20.txt 7 ms 4352 KB
1_21.txt 7 ms 4352 KB
1_22.txt 7 ms 4352 KB
1_23.txt 7 ms 4352 KB
1_24.txt 7 ms 4352 KB
1_25.txt 7 ms 4352 KB
1_26.txt 7 ms 4352 KB
1_27.txt 7 ms 4352 KB
1_28.txt 7 ms 4352 KB
1_29.txt 7 ms 4352 KB
1_30.txt 7 ms 4352 KB
1_31.txt 7 ms 4352 KB
1_32.txt 7 ms 4352 KB
1_33.txt 7 ms 4352 KB
1_34.txt 7 ms 4352 KB
1_35.txt 7 ms 4352 KB
1_36.txt 7 ms 4352 KB
1_37.txt 7 ms 4352 KB
1_38.txt 7 ms 4352 KB
1_39.txt 7 ms 4352 KB
1_40.txt 7 ms 4352 KB
1_41.txt 7 ms 4352 KB
1_42.txt 7 ms 4352 KB
1_43.txt 7 ms 4352 KB
1_44.txt 7 ms 4352 KB
1_45.txt 7 ms 4352 KB
1_46.txt 7 ms 4352 KB
1_47.txt 7 ms 4352 KB
1_48.txt 7 ms 4352 KB
1_49.txt 7 ms 4352 KB
1_50.txt 7 ms 4352 KB
1_51.txt 7 ms 4352 KB
1_52.txt 7 ms 4352 KB
1_53.txt 7 ms 4352 KB