結果
問題 | No.6 使いものにならないハッシュ |
ユーザー | むらため |
提出日時 | 2020-06-01 08:31:35 |
言語 | Nim (2.0.2) |
結果 |
AC
|
実行時間 | 17 ms / 5,000 ms |
コード長 | 3,854 bytes |
コンパイル時間 | 5,842 ms |
コンパイル使用メモリ | 71,140 KB |
実行使用メモリ | 4,376 KB |
最終ジャッジ日時 | 2023-10-14 23:24:36 |
合計ジャッジ時間 | 7,414 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,348 KB |
testcase_01 | AC | 2 ms
4,352 KB |
testcase_02 | AC | 17 ms
4,352 KB |
testcase_03 | AC | 4 ms
4,348 KB |
testcase_04 | AC | 5 ms
4,348 KB |
testcase_05 | AC | 6 ms
4,348 KB |
testcase_06 | AC | 9 ms
4,352 KB |
testcase_07 | AC | 6 ms
4,352 KB |
testcase_08 | AC | 8 ms
4,348 KB |
testcase_09 | AC | 5 ms
4,352 KB |
testcase_10 | AC | 2 ms
4,352 KB |
testcase_11 | AC | 5 ms
4,348 KB |
testcase_12 | AC | 12 ms
4,352 KB |
testcase_13 | AC | 5 ms
4,376 KB |
testcase_14 | AC | 5 ms
4,348 KB |
testcase_15 | AC | 10 ms
4,352 KB |
testcase_16 | AC | 7 ms
4,352 KB |
testcase_17 | AC | 13 ms
4,352 KB |
testcase_18 | AC | 16 ms
4,348 KB |
testcase_19 | AC | 12 ms
4,352 KB |
testcase_20 | AC | 11 ms
4,352 KB |
testcase_21 | AC | 4 ms
4,352 KB |
testcase_22 | AC | 11 ms
4,352 KB |
testcase_23 | AC | 11 ms
4,348 KB |
testcase_24 | AC | 11 ms
4,376 KB |
testcase_25 | AC | 6 ms
4,352 KB |
testcase_26 | AC | 13 ms
4,348 KB |
testcase_27 | AC | 10 ms
4,352 KB |
testcase_28 | AC | 7 ms
4,352 KB |
testcase_29 | AC | 14 ms
4,348 KB |
testcase_30 | AC | 13 ms
4,352 KB |
testcase_31 | AC | 11 ms
4,348 KB |
コンパイルメッセージ
/home/judge/data/code/Main.nim(74, 36) Warning: toU8 is deprecated [Deprecated] /home/judge/data/code/Main.nim(1, 50) Warning: imported and not used: 'sugar' [UnusedImport] /home/judge/data/code/Main.nim(1, 26) Warning: imported and not used: 'strscans' [UnusedImport]
ソースコード
import sequtils,strutils,strscans,algorithm,math,sugar,sets,tables,macros macro unpack*(rhs: seq,cnt: static[int]): auto = let t = genSym(); result = quote do:(let `t` = `rhs`;()) for i in 0..<cnt: result[0][1].add(quote do:`t`[`i`]) template get*():string = stdin.readLine() template times*(n:int,body:untyped): untyped = (for _ in 0..<n: body) template `max=`*(x,y:typed):void = x = max(x,y) template `min=`*(x,y:typed):void = x = min(x,y) type Queue* [T] = object ## A queue. data: seq[T] rd, wr, count, mask: int proc initQueue*[T](initialSize: int = 4): Queue[T] = assert isPowerOfTwo(initialSize) result.mask = initialSize-1 newSeq(result.data, initialSize) proc len*[T](q: Queue[T]): int {.inline.}= result = q.count proc front*[T](q: Queue[T]): T {.inline.}= result = q.data[q.rd] proc back*[T](q: Queue[T]): T {.inline.} = result = q.data[q.wr - 1 and q.mask] proc `[]`*[T](q: Queue[T], i: Natural) : T {.inline.} = return q.data[q.rd + i and q.mask] proc `[]`*[T](q: var Queue[T], i: Natural): var T {.inline.} = return q.data[q.rd + i and q.mask] proc `[]=`* [T] (q: var Queue[T], i: Natural, val : T) {.inline.} = q.data[q.rd + i and q.mask] = val iterator items*[T](q: Queue[T]): T = var i = q.rd for c in 0 ..< q.count: yield q.data[i] i = (i + 1) and q.mask iterator pairs*[T](q: Queue[T]): tuple[key: int, val: T] = var i = q.rd for c in 0 ..< q.count: yield (c, q.data[i]) i = (i + 1) and q.mask proc add*[T](q: var Queue[T], item: T) = var cap = q.mask+1 if unlikely(q.count >= cap): var n = newSeq[T](cap*2) for i, x in pairs(q): # don't use copyMem because the GC and because it's slower. shallowCopy(n[i], x) shallowCopy(q.data, n) q.mask = cap*2 - 1 q.wr = q.count q.rd = 0 inc q.count q.data[q.wr] = item q.wr = (q.wr + 1) and q.mask template default[T](t: typedesc[T]): T = var v: T v proc pop*[T](q: var Queue[T]): T {.inline, discardable.} = dec q.count result = q.data[q.rd] q.data[q.rd] = default(type(result)) q.rd = (q.rd + 1) and q.mask proc enqueue*[T](q: var Queue[T], item: T) = q.add(item) proc dequeue*[T](q: var Queue[T]): T = q.pop() proc `$`*[T](q: Queue[T]): string = result = "[" for x in items(q): # Don't remove the items here for reasons that don't fit in this margin. if result.len > 1: result.add(", ") result.add($x) result.add("]") proc `+=`[T](x:var set[T],y:T):void = x.incl(y) proc `-=`[T](x:var set[T],y:T):void = x.excl(y) proc `+=`[T](x:var set[T],y:set[T]):void = x = x.union(y) proc `*=`[T](x:var set[T],y:set[T]):void = x = x.intersection(y) proc `-=`[T](x:var set[T],y:set[T]):void = x = x.difference(y) converter toInt8(x:int) : int8 = x.toU8() proc parseDecimal(n:int) : auto = ($n).mapIt(it.ord - '0'.ord) proc getIsPrimes(n:int) :seq[bool] = # [0...n] result = newSeqWith(n+1,true) result[0] = false result[1] = false for i in 2..n.float.sqrt.int : if not result[i]: continue for j in countup(i*2,n,i): result[j] = false proc getPrimes(n:int,start:int = 0):seq[int] = # [2,3,5,...n] let isPrime = getIsPrimes(n) result = @[] for i,p in isPrime: if i < start: continue if p : result &= i proc hash(n:int) : int = result = ($n).mapIt(it.ord - '0'.ord).sum() if result > 9: result = hash(result) # hash は 0,3,6,9にならない (3は一度だけ) => 124578の6が最大だが、大きい方を優先するので途中でbreakはできない let K = get().parseInt N = get().parseInt primes = getPrimes(N,start=K) var L = 0 hashes : set[int8] = {} ans = (prime:0, card:0) for i,p in primes: let h = hash(p) if h in hashes: while h in hashes: hashes -= hash(primes[L]) L += 1 hashes += h if hashes.card >= ans.card: ans.prime = primes[L] ans.card = hashes.card echo ans.prime