結果
問題 | No.7 プライムナンバーゲーム |
ユーザー | phspls |
提出日時 | 2020-06-02 22:39:43 |
言語 | Rust (1.77.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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 1,535 ms
5,248 KB |
testcase_03 | AC | 36 ms
5,248 KB |
testcase_04 | AC | 7 ms
5,248 KB |
testcase_05 | AC | 7 ms
5,248 KB |
testcase_06 | AC | 276 ms
5,248 KB |
testcase_07 | AC | 162 ms
5,248 KB |
testcase_08 | AC | 55 ms
5,248 KB |
testcase_09 | AC | 492 ms
5,248 KB |
testcase_10 | AC | 1 ms
5,248 KB |
testcase_11 | AC | 163 ms
5,248 KB |
testcase_12 | AC | 958 ms
5,248 KB |
testcase_13 | AC | 1,051 ms
5,248 KB |
testcase_14 | AC | 1,539 ms
5,248 KB |
testcase_15 | AC | 1,424 ms
5,248 KB |
testcase_16 | AC | 1,270 ms
5,248 KB |
ソースコード
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" }); }