QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#289004 | #7863. Parity Game | ucup-team635# | TL | 0ms | 0kb | Rust | 10.1kb | 2023-12-23 14:42:34 | 2023-12-23 14:42:35 |
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 +