結果
問題 | No.7 プライムナンバーゲーム |
ユーザー | keymoon |
提出日時 | 2020-02-05 17:44:23 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 86 ms / 5,000 ms |
コード長 | 2,600 bytes |
コンパイル時間 | 1,132 ms |
コンパイル使用メモリ | 118,116 KB |
実行使用メモリ | 27,220 KB |
最終ジャッジ日時 | 2024-10-01 16:30:36 |
合計ジャッジ時間 | 2,298 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 25 ms
26,908 KB |
testcase_01 | AC | 25 ms
27,188 KB |
testcase_02 | AC | 86 ms
26,836 KB |
testcase_03 | AC | 29 ms
23,088 KB |
testcase_04 | AC | 27 ms
25,020 KB |
testcase_05 | AC | 26 ms
26,948 KB |
testcase_06 | AC | 45 ms
24,868 KB |
testcase_07 | AC | 40 ms
26,932 KB |
testcase_08 | AC | 32 ms
26,936 KB |
testcase_09 | AC | 55 ms
24,892 KB |
testcase_10 | AC | 24 ms
27,036 KB |
testcase_11 | AC | 37 ms
26,784 KB |
testcase_12 | AC | 70 ms
27,032 KB |
testcase_13 | AC | 71 ms
22,964 KB |
testcase_14 | AC | 85 ms
27,220 KB |
testcase_15 | AC | 86 ms
26,832 KB |
testcase_16 | AC | 78 ms
25,140 KB |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.IO; using System.Linq; using System.Collections; using System.Collections.Generic; using System.Numerics; using System.Diagnostics; using System.Text; using System.Text.RegularExpressions; using System.Threading.Tasks; using static System.Math; using MethodImplOptions = System.Runtime.CompilerServices.MethodImplOptions; using MethodImplAttribute = System.Runtime.CompilerServices.MethodImplAttribute; static class P { static void Main() { int n = int.Parse(Console.ReadLine()); var primes = Primes(n).ToArray(); bool[] canWin = new bool[n + 1]; canWin[0] = true; canWin[1] = true; for (int i = 2; i < canWin.Length; i++) { foreach (var item in primes.TakeWhile(x => x <= i)) { if (canWin[i - item]) continue; canWin[i] = true; break; } } Console.WriteLine(canWin.Last() ? "Win" : "Lose"); } public static IEnumerable<int> Primes(int n) { if (n < 2) yield break; yield return 2; ulong[] bitArray = new ulong[(n + 1) / 2 / 64 + 1]; int[] smallPrimes = { 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61 }; foreach (var prime in smallPrimes) { if (n < prime) yield break; yield return prime; ulong[] mask = new ulong[prime]; for (int j = (prime - 3) >> 1; j < (prime << 6); j += prime) mask[j >> 6] |= 1UL << j; int maskInd = 0; for (int i = 0; i < bitArray.Length; i++) { bitArray[i] |= mask[maskInd]; if (++maskInd >= prime) maskInd = 0; } } int[] deBruijnIndex = { 0, 1, 59, 2, 60, 40, 54, 3, 61, 32, 49, 41, 55, 19, 35, 4, 62, 52, 30, 33, 50, 12, 14, 42, 56, 16, 27, 20, 36, 23, 44, 5, 63, 58, 39, 53, 31, 48, 18, 34, 51, 29, 11, 13, 15, 26, 22, 43, 57, 38, 47, 17, 28, 10, 25, 21, 37, 46, 9, 24, 45, 8, 7, 6 }; int maxInd = n / 2; for (int i = 0; i < bitArray.Length; i++) { for (ulong bit = ~bitArray[i]; bit != 0; bit &= bit - 1) { int index = i << 6 | deBruijnIndex[((bit & (~bit + 1)) * 0x03F566ED27179461UL) >> 58]; int prime = (index << 1) + 3; if (n < prime) yield break; yield return prime; for (int ind = index; ind <= maxInd; ind += prime) bitArray[ind >> 6] |= 1UL << ind; } } } }