QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#289004#7863. Parity Gameucup-team635#TL 0ms0kbRust10.1kb2023-12-23 14:42:342023-12-23 14:42:35

Judging History

你现在查看的是最新测评结果

  • [2023-12-23 14:42:35]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2023-12-23 14:42:34]
  • 提交

answer

// 隣接2項について
// and, xor
// のどちらかをやる
// 最終的にtを残すとAlicdの勝ち、そうでないならbobの価値
// これをインタラクティブとしてジャッジと勝負
//
// 00 -> 0
// それ以外はand, xor で01好きな方を作れる
// T=0の時
// 最後に操作するのがAliceなら勝ち
// bobなら 00以外を残せばbobの勝ち
// N が偶数ならAliceが勝つ
// 奇数の場合、bobは00ができないように動く
// Aliceは00ができるように動く
// 0が入力にあればAliceが勝つっぽい?
// そうでもない
// 00 があったら勝てる
// それ以外で勝てるパターンは?
// 常に0を生成できる
// 0が存在すればいい...というわけでもない
// bobは00ができないように動くのが大前提
// 端に0があるなら両端0でbobに回せるので勝てる
// それ以外
//
// A_i = 0 (i % 2 == 0) なるiがあればAliceの勝ち
//
//
// T=1 の時
// 最後に操作するのがbobなら何残ってても勝ち
// Aliceなら00以外を残せばいい

use std::collections::*;
use std::io::Write;

type Map<K, V> = BTreeMap<K, V>;
type Set<T> = BTreeSet<T>;
type Deque<T> = VecDeque<T>;

fn main() {
    test();
    let (n, t) = {
        let a = read();
        (a[0].parse::<usize>().unwrap(), a[1].parse::<u32>().unwrap())
    };
    let mut a = {
        let a = read();
        a.into_iter()
            .map(|a| a.parse::<u32>().unwrap())
            .collect::<Vec<_>>()
    };
    /*
    if n == 1 {
        if a[0] == t {
            println!("Alice");
        } else {
            println!("Bob");
        }
        return;
    }
    */
    let operation = |a: &mut Vec<u32>, p: usize, c: &str| {
        assert!(0 < p && p < a.len());
        let v = a.remove(p);
        if c == "+" {
            a[p - 1] ^= v;
        } else {
            a[p - 1] &= v;
        }
    };
    let opposite = |a: &mut Vec<u32>| {
        let (p, c) = {
            let a = read();
            (a[0].parse::<usize>().unwrap(), a[1].clone())
        };
        assert!(p > 0);
        operation(a, p, &c);
    };
    let mine = |a: &mut Vec<u32>, x: usize, c: &str| {
        println!("{} {}", x, c);
        operation(a, x, c);
    };
    if t == 0 {
        if n % 2 == 0 || a.iter().step_by(2).any(|a| *a == 0) {
            println!("Alice");
            while a.len() > 1 {
                if a[0] != 0 {
                    let x = a[0];
                    let y = a[1];
                    if (x, y) == (1, 1) {
                        mine(&mut a, 1, "+");
                    } else {
                        mine(&mut a, 1, "*");
                    }
                } else {
                    let n = a.len();
                    let x = a[n - 2];
                    let y = a[n - 1];
                    if (x, y) == (1, 1) {
                        mine(&mut a, n - 1, "+");
                    } else {
                        mine(&mut a, n - 1, "*");
                    }
                }
                if a.len() > 1 {
                    opposite(&mut a);
                }
            }
        } else {
            println!("Bob");
            while a.len() > 1 {
                opposite(&mut a);
                if a.len() > 1 {
                    let n = a.len();
                    for i in 1..n {
                        let mut b = a.clone();
                        let v = b.remove(i);
                        let u = b[i - 1];
                        b[i - 1] |= v;
                        if b.iter().step_by(2).all(|b| *b == 1) {
                            if (v, u) == (1, 1) {
                                mine(&mut a, i, "*");
                            } else {
                                mine(&mut a, i, "+");
                            }
                            break;
                        }
                    }
                    assert!(a.len() < n);
                }
            }
        }
    } else {
        let mut alice = false;
        alice |= (1..a.len()).any(|x| {
            let mut a = a.clone();
            let v = a.remove(x);
            a[x - 1] |= v;
            a.iter().step_by(2).all(|a| *a == 1)
        });
        if n % 2 == 1 {
            alice = false;
        }
        if alice {
            println!("Alice");
            while a.len() > 1 {
                let x = (1..a.len()).find(|&x| {
                    let mut a = a.clone();
                    let v = a.remove(x);
                    a[x - 1] |= v;
                    a.iter().step_by(2).all(|a| *a == 1)
                }).unwrap();
                let (v, u) = (a[x], a[x - 1]);
                if (v, u) == (1, 1) {
                    mine(&mut a, x, "*");
                } else {
                    mine(&mut a, x, "+");
                }
                if a.len() > 1 {
                    opposite(&mut a);
                }
            }
        } else {
            println!("Bob");
            while a.len() > 1 {
                opposite(&mut a);
                if a.len() > 1 {
                    let n = a.len();
                    for i in 1..n {
                        let mut b = a.clone();
                        let v = b.remove(i);
                        let u = b[i - 1];
                        b[i - 1] |= v;
                        if n % 2 == 0 || b.iter().step_by(2).all(|b| *b == 1) {
                            if (v, u) == (1, 1) {
                                mine(&mut a, i, "+");
                            } else {
                                mine(&mut a, i, "*");
                            }
                            break;
                        }
                    }
                    assert!(a.len() < n);
                }
            }
        }
    }
}

fn read() -> Vec<String> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim()
        .split_whitespace()
        .map(|s| String::from(s))
        .collect()
}

fn test() {
    let mut memo = Map::new();
    let mut used = Set::new();
    for _ in 0..1000000 {
        let n = rand() % 16 + 1;
        let t = (rand() % 2) as u8;
        let a = (0..n)
            .map(|_| (rand() % 100 < 50) as u8)
            .collect::<Vec<_>>();
        if !used.insert((a.clone(), t)) {
            continue;
        }
        let win = dfs(a.clone(), t as u8, &mut memo);
        let predict = if t == 0 {
            if n % 2 == 0 {
                true
            } else {
                a.iter().step_by(2).any(|a| *a == 0)
            }
        } else {
            if n == 1 {
                a[0] == t
            } else if n % 2 == 1 {
                false
            } else {
                (1..a.len()).any(|x| {
                    let mut a = a.clone();
                    let v = a.remove(x);
                    a[x - 1] |= v;
                    a.iter().step_by(2).all(|a| *a == 1)
                })
            }
        };
        if predict != win {
            println!("{:?} {}: {}", a, t, win);
        }
    }
}

// Aliceが勝つか
fn dfs(a: Vec<u8>, t: u8, memo: &mut Map<(Vec<u8>, u8), bool>) -> bool {
    if let Some(&v) = memo.get(&(a.clone(), t)) {
        return v;
    }
    if a.len() == 1 {
        return a[0] == t;
    }
    if a.len() == 2 {
        let (x, y) = (a[0], a[1]);
        return x & y == t || x ^ y == t;
    }
    let win = (1..a.len()).any(|x| {
        let mut a = a.clone();
        let v = a.remove(x);
        let val = [a[x - 1] & v, a[x - 1] ^ v];
        for v in val {
            a[x - 1] = v;
            if (1..a.len()).all(|x| {
                let mut a = a.clone();
                let v = a.remove(x);
                let val = [a[x - 1] & v, a[x - 1] ^ v];
                !val.iter().any(|&v| {
                    let mut a = a.clone();
                    a[x - 1] = v;
                    !dfs(a, t, memo)
                })
            }) {
                return true;
            }
        }
        false
    });
    memo.insert((a, t), win);
    win
}

// ---------- begin input macro ----------
// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[macro_export]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

#[macro_export]
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

#[macro_export]
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, bytes) => {
        read_value!($iter, String).bytes().collect::<Vec<u8>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
// ---------- end input macro ----------
fn rand_memory() -> usize {
    Box::into_raw(Box::new("I hope this is a random number")) as usize
}

fn rand() -> usize {
    static mut X: usize = 0;
    unsafe {
        if X == 0 {
            X = rand_memory();
        }
        X ^= X << 13;
        X ^= X >> 17;
        X ^= X << 5;
        X
    }
}

fn shuffle<T>(a: &mut [T]) {
    for i in 1..a.len() {
        let p = rand() % (i + 1);
        a.swap(i, p);
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

4 1
0 1 0 1
1 *
1

output:

Alice
1 +
1 +

result: