Submission #2444358


Source Code Expand

fn main() {
    let mut sc = Scanner::new();
    let n: usize = sc.read();
    let a: Vec<u64> = (0..n).map(|_| sc.read()).collect();

    let mut grundy = 0;
    for &a in &a {
        grundy ^= a;
    }

    let mut used = vec![false; n];
    for pos in (0..32).rev() {
        if grundy & (1 << pos) == 0 {
            continue;
        }
        for i in 0..n {
            if used[i] {
                continue;
            }

            let tmp = a[i] ^ (a[i] - 1);
            let check = (1 << (pos + 1)) - 1;
            if tmp == check {
                grundy ^= tmp;
                used[i] = true;
                break;
            }
        }
    }

    if grundy == 0 {
        println!(
            "{}",
            used.iter().map(|&b| if b { 1 } else { 0 }).sum::<usize>()
        );
    } else {
        println!("-1");
    }
}

struct Scanner {
    ptr: usize,
    length: usize,
    buf: Vec<u8>,
    small_cache: Vec<u8>,
}

impl Scanner {
    fn new() -> Scanner {
        Scanner {
            ptr: 0,
            length: 0,
            buf: vec![0; 1024],
            small_cache: vec![0; 1024],
        }
    }

    fn load(&mut self) {
        use std::io::Read;
        let mut s = std::io::stdin();
        self.length = s.read(&mut self.buf).unwrap();
    }

    fn byte(&mut self) -> u8 {
        if self.ptr >= self.length {
            self.ptr = 0;
            self.load();
            if self.length == 0 {
                self.buf[0] = b'\n';
                self.length = 1;
            }
        }

        self.ptr += 1;
        return self.buf[self.ptr - 1];
    }

    fn is_space(b: u8) -> bool {
        b == b'\n' || b == b'\r' || b == b'\t' || b == b' '
    }

    fn read<T>(&mut self) -> T
    where
        T: std::str::FromStr,
        T::Err: std::fmt::Debug,
    {
        let mut b = self.byte();
        while Scanner::is_space(b) {
            b = self.byte();
        }

        for pos in 0..self.small_cache.len() {
            self.small_cache[pos] = b;
            b = self.byte();
            if Scanner::is_space(b) {
                return String::from_utf8_lossy(&self.small_cache[0..(pos + 1)])
                    .parse()
                    .unwrap();
            }
        }

        let mut v = self.small_cache.clone();
        while !Scanner::is_space(b) {
            v.push(b);
            b = self.byte();
        }
        return String::from_utf8_lossy(&v).parse().unwrap();
    }
}

Submission Info

Submission Time
Task C - Cheating Nim
User kenkoooo
Language Rust (1.15.1)
Score 500
Code Size 2571 Byte
Status AC
Exec Time 10 ms
Memory 4352 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 2
AC × 26
Set Name Test Cases
Sample example0.txt, example1.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, example0.txt, example1.txt
Case Name Status Exec Time Memory
000.txt AC 2 ms 4352 KB
001.txt AC 2 ms 4352 KB
002.txt AC 10 ms 4352 KB
003.txt AC 4 ms 4352 KB
004.txt AC 5 ms 4352 KB
005.txt AC 4 ms 4352 KB
006.txt AC 10 ms 4352 KB
007.txt AC 9 ms 4352 KB
008.txt AC 9 ms 4352 KB
009.txt AC 9 ms 4352 KB
010.txt AC 9 ms 4352 KB
011.txt AC 9 ms 4352 KB
012.txt AC 10 ms 4352 KB
013.txt AC 9 ms 4352 KB
014.txt AC 9 ms 4352 KB
015.txt AC 9 ms 4352 KB
016.txt AC 9 ms 4352 KB
017.txt AC 9 ms 4352 KB
018.txt AC 9 ms 4352 KB
019.txt AC 9 ms 4352 KB
020.txt AC 9 ms 4352 KB
021.txt AC 2 ms 4352 KB
022.txt AC 3 ms 4352 KB
023.txt AC 10 ms 4352 KB
example0.txt AC 2 ms 4352 KB
example1.txt AC 2 ms 4352 KB