結果
問題 | No.7 プライムナンバーゲーム |
ユーザー |
|
提出日時 | 2020-06-02 22:39:43 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 1,539 ms / 5,000 ms |
コード長 | 1,328 bytes |
コンパイル時間 | 11,707 ms |
コンパイル使用メモリ | 377,212 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-01 16:35:37 |
合計ジャッジ時間 | 21,651 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
fn get_primes(n: usize) -> Vec<usize> { let mut flgs: Vec<bool> = vec![true; n+1]; flgs[0] = false; flgs[1] = false; if n < 2 { return vec![]; } let lim = (n as f64).sqrt().ceil() as usize + 1; for i in 2..=lim { if !flgs[i] { continue; } for j in i..=n/i { flgs[i*j] = false; } } flgs.iter().enumerate().filter(|pair| *pair.1).map(|pair| pair.0).collect() } fn main() { //TODO let mut n = String::new(); std::io::stdin().read_line(&mut n).ok(); let n: usize = n.trim().parse().unwrap(); let primes: Vec<usize> = get_primes(n); let mut result: Vec<Option<usize>> = vec![None; n+1]; result[2] = Some(0); if n > 2 { result[3] = Some(0); } for i in 4..=n { let mut temp: Vec<usize> = vec![]; for p in primes.iter() { if *p > i - 2 { break; } if temp.contains(&p) { continue; } temp.push(result[i - p].unwrap()); } temp.sort(); let mut flg = false; for j in 0..temp.len() { if j == temp[j] { continue; } flg = true; result[i] = Some(j); break; } if !flg { result[i] = Some(temp.len()); } } println!("{}", if result[n] == Some(0) { "Lose" } else { "Win" }); }