結果
問題 | No.715 集合と二人ゲーム |
ユーザー |
![]() |
提出日時 | 2017-10-04 14:18:16 |
言語 | Rust (1.83.0 + proconio) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,206 bytes |
コンパイル時間 | 13,659 ms |
コンパイル使用メモリ | 378,596 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-17 09:35:57 |
合計ジャッジ時間 | 17,286 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 WA * 28 |
ソースコード
// OEIS A002187 https://oeis.org/A002187use std::io::*;use std::str::*;fn readw<T: FromStr, R: Read>(s: &mut R) -> Option<T> {let s = s.bytes().map(|c| c.unwrap() as char).skip_while(|c| c.is_whitespace()).take_while(|c| !c.is_whitespace()).collect::<String>();if s.is_empty() {None} else {s.parse::<T>().ok()}}const MAX_N: usize = 1000;fn read<T: FromStr, R: Read>(s: &mut R) -> T {readw(s).unwrap_or_else(|| std::process::exit(1))}fn grundy(n: u32, dp: &mut Vec<Option<u32>>) -> u32 {if n < 340 {grundy_rec(n, dp)} else {grundy_rec((n - 340) % 34, dp)}}fn grundy_rec(n: u32, dp: &mut Vec<Option<u32>>) -> u32 {if let Some(res) = dp[n as usize] {res} else {let res = if n <= 2 {n} else {let mut s = vec![false; MAX_N];if n >= 4 {for i in 1..n-3 {s[(grundy_rec(i, dp) ^ grundy_rec(n - 3 - i, dp)) as usize] = true;}}s[grundy_rec(n - 2, dp) as usize] = true;s[grundy_rec(n - 3, dp) as usize] = true;(0..MAX_N).find(|&x| !s[x]).unwrap() as u32};dp[n as usize] = Some(res);// println!("{} {}", n, res);res}}fn solve() {// let mut dp = vec![None; 100];// for i in 1..100 {// print!("{}, ", grundy(i, &mut dp));// }let s = stdin();let s = s.lock();let s = &mut BufReader::new(s);let n: usize = read(s);let mut a: Vec<u32> = (0..n).map(|_| read(s)).collect();a.sort();let mut g = 0;let mut dp = vec![None; n + 1];let mut i = 0;while i < n {let mut j = i;while j + 1 < n && a[j + 1] == a[j] + 1 {j += 1;}// [i,j]let k = j - i + 1;g ^= grundy(k as u32, &mut dp);i = j + 1;}println!("{}", if g == 0 { "Second" } else { "First" });}fn main() {let stack_size = 104_857_600; // 100 MBlet thd = std::thread::Builder::new().stack_size(stack_size);thd.spawn(solve).unwrap().join().unwrap();}