結果

問題 No.826 連絡網
ユーザー nimonnimon
提出日時 2019-05-23 22:50:51
言語 Nim
(2.0.0)
結果
WA  
実行時間 -
コード長 1,924 bytes
コンパイル時間 5,917 ms
コンパイル使用メモリ 107,240 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-14 18:37:34
合計ジャッジ時間 7,241 ms
ジャッジサーバーID
(参考情報)
judge11 / judge12
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 AC 1 ms
4,376 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 AC 2 ms
4,376 KB
testcase_15 WA -
testcase_16 AC 1 ms
4,376 KB
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 AC 2 ms
4,380 KB
testcase_30 AC 2 ms
4,380 KB
testcase_31 AC 2 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

from sequtils import newSeqWith, mapIt

proc isSetBit*(bits: uint64, index: range[0..63]): bool {.inline.} =
  return ((bits shr index) and 1) != 0

proc unsetBit*(bits: var uint64; i: range[0..63]) {.inline.} =
    bits = bits and (not (1'u64 shl i))

proc isPrime(s: seq[uint64]; p: int): bool =
  s[p div 64].isSetBit(p mod 64)

const
  maxN = 1_000_000
  sqrtMaxN = 1_000
  L = (maxN + 1 + 64 - 1) div 64
proc sieve*(): seq[uint64] =
  result = newSeqWith(L, not 0'u64)
  for i in 2..sqrtMaxN:
    if result.isPrime(i):
      for j in countup(i * i, maxN, i):
        result[j div 64].unsetBit(j mod 64)

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
from strutils import split, parseInt, toBin
from bitops import popcount

const s = sieve()

var N, P: int
(N, P) = stdin.readLine.split.mapIt(it.parseInt)

proc maskLeft(x: uint64; i: int): uint64 =
  ## x の i ビット目未満を 0 にする
  if i >= 64: x
  else: x and (not ((1'u64 shl i) - 1))

proc maskRight(x: uint64; i: int): uint64 =
  ## x の i ビット目より上を 0 にする
  if i < 0: 0'u64
  else: x and ((1'u64 shl (i + 1)) - 1)

proc f(s: seq[uint64]; N: int): int =
  let
    l = N div 2 + 1
    r = N
    l64 = l div 64
    r64 = r div 64
  if l64 == r64:
    result = (N + 1) div 2 - s[0].maskLeft(l).maskRight(r).popcount
  else:
    result = 64 - N div 2 mod 64 - s[l64].maskLeft(l).popcount
    for i in (l64 + 1)..(r64 - 1):
      result += 64 - s[i].popcount
    result += N mod 64 - s[r64].maskRight(r).popcount

  # echo s[l64..r64].mapIt(it.BiggestInt.toBin(64)), " | ", N, " | ", result, " | ", [l, r], " | ", [l64, r64], " | ", [l mod 64, r mod 64]
  # echo s[l64].maskLeft(l).BiggestInt.toBin(64)
  # echo s[r64].maskRight(r).BiggestInt.toBin(64)
  # echo s[l64].maskLeft(l).maskRight(r).BiggestInt.toBin(64)

if P <= 1 or (P >= N div 2 and s.isPrime(P)):
  echo "1"
else:
  echo N div 2 - 1 + f(s, N)
0